有关《查找两个List中的不同元素》的问题解答与编程实践

 

 郑海波 2013-07-08

问题：

有List<String> list1和List<String> list2,两个集合各有上万个元素，怎样查找两个集合中不同的元素呢?

问题分析：

由于每个list中都有上万个元素，如果用简单的遍历查找算法，那么至少需要10000*10000次判断比较。显然，这样做的效率极低。那么有没有比较好的方案呢？经过我的思考，想出了2个办法。请大家评判。

方法一：遍历算法的改进算法

思路：对每一个list1中的元素，都在list2中查找一下，是否重复，如果不重复，则将该元素放到listDiff中。如果重复，则将该元素从list2中剔除。这样，能够减少遍历算法的时间复杂度，而且重复元素越多，该改进算法的运行时间就越短。当然，如果两个list的重复元素个数远远小于list的长度，则该算法的时间复杂度和遍历算法近似相同，会变的很慢而不切实际。

方法二：利用Map中无重复元素的特性

思路：将list1中元素首先复制到map<String,Integer>中,并将其Integer的值设置为1.然后再对list2中的元素，与map中元素比较。如果map中已经存在该String，那么map中对应String的Integer加1（表示字符串出现的次数），如果map中不存在，那么就将其复制到map中，并设置其Integer为1.那么，map中Integer值为1的元素所对应的String，就是两个list中不同的元素。

以下代码是在Java中实现，也可以用C++ STL进行测试。

[java] view plaincopy
 
  1. import java.util.ArrayList;  
  2. import java.util.HashMap;  
  3. import java.util.List;  
  4. import java.util.Map;  
  5. /*  
  6.  *@author: ZhengHaibo     
  7.  *2013-07-08  Nanjing,Conris,China  
  8.  */   
  9. public class TestMian {  
  10.     private static final int ListLen = 10000;// 设置list的长度  
  11.     private static final Integer flagUnique = 1;//无重复字符串的键值  
  12.     public List<String> list1 = new ArrayList<String>();  
  13.     public List<String> list2 = new ArrayList<String>();  
  14.   
  15.     public static void main(String[] args) {  
  16.         // TODO Auto-generated method stub  
  17.         TestMian mTest=new TestMian();  
  18.         mTest.initList();  
  19.         List<String> listDiff1=mTest.getDiffElementUseEach(mTest.list1,mTest.list2);//获得不同元素  
  20.         mTest.initList();  
  21.         List<String> listDiff2=mTest.getDiffElementUseMap(mTest.list1,mTest.list2);//获得不同元素  
  22.         System.out.println("The number of diff element is: "+listDiff1.size());  
  23.         System.out.println("The number of diff element is: "+listDiff2.size());  
  24.         //mTest.printList(listDiff1);  
  25.         //mTest.printList(listDiff2);  
  26.     }  
  27.     // 初始化list中的元素，并保证有相同的元素  
  28.     public void initList() {  
  29.         list1.clear();  
  30.         list2.clear();  
  31.         for (int i = 0; i < ListLen; i++) {  
  32.             list1.add("conris_list_of" + i + "test");  
  33.             list2.add("conris_list_of" + 3 * i + "test");  
  34.         }  
  35.     }  
  36.     //获得连个list中的不同元素，查找删除法  
  37.     public List<String> getDiffElementUseEach(List<String> list1,List<String> list2) {  
  38.         System.out.println("-----------------------方法1----------------------");  
  39.         long runtime = System.nanoTime();// 开始计时  
  40.         List<String> diffList = new ArrayList<String>();// 用于保存两个list中不同的元素  
  41.         for (String string:list1) {//消除list1本身的重复元素  
  42.             int index=list2.indexOf(string);  
  43.             if (index==-1) {//说明list2中不存在此元素  
  44.                 diffList.add(string);  
  45.             }else{//list2存在此元素，那么删除此元素  
  46.                 list2.remove(index);  
  47.             }  
  48.         }  
  49.         for(String string:list2){//此时，liat2中的重复元素已经删除了，只需要复制到diffList中即可  
  50.             diffList.add(string);  
  51.         }  
  52.         System.out.println("getDiffElementUseRemove run time:"  
  53.                 + (System.nanoTime() - runtime));  
  54.         return diffList;  
  55.     }  
  56.     //获得两个list中的不同元素，map方法  
  57.     public List<String> getDiffElementUseMap(List<String> list1,List<String> list2){  
  58.         System.out.println("-----------------------方法2----------------------");  
  59.         long runtime = System.nanoTime();//开始计时  
  60.         //利用map中不能有重复元素的特点  
  61.         Map<String, Integer> map = new HashMap<String,Integer>(list1.size()+ list2.size());  
  62.         List<String> diffList = new ArrayList<String>();//用于保存两个list中不同的元素  
  63.         for (String string : list1) {  
  64.             map.put(string,flagUnique);//先将list1中元素复制到map中保存  
  65.         }  
  66.         for (String string : list2) {  
  67.             Integer key = map.get(string);// 获得键值  
  68.             if (key != null) {//如果map中已经存在该元素，说明list1中存在该元素，那么将其key加1  
  69.                 map.put(string, ++key);  
  70.                 continue;  
  71.             }else{//如果不存在，则放入map中  
  72.                 map.put(string,flagUnique);  
  73.             }  
  74.         }  
  75.         for (Map.Entry<String, Integer> entry : map.entrySet()){  
  76.             if (entry.getValue() == flagUnique)//在map中，键值为flagUnique的元素即为无重复的元素  
  77.             {  
  78.                 diffList.add(entry.getKey());  
  79.             }  
  80.         }  
  81.         System.out.println("getDiffElementUseMap run time:"  
  82.                 + (System.nanoTime() - runtime));  
  83.         return diffList;  
  84.     }  
  85.     public void printList(List<String> list){  
  86.         for(int i=0;i<list.size();i++){  
  87.             System.out.println(list.get(i));  
  88.         }  
  89.     }  
  90. }  

实验结果：

当ListLen设置为10000时：

结果1：

[html] view plaincopy
 
  1. -----------------------方法1----------------------  
  2. getDiffElementUseRemove run time:2015792051  
  3. -----------------------方法2----------------------  
  4. getDiffElementUseMap run time:37966034  
  5. The number of diff element is: 13332  
  6. The number of diff element is: 13332  

当ListLen设置为100000时：等了半天方法1没有运行出来结果，方法2的运行结果如下：
[html] view plaincopy
 
  1. -----------------------方法2----------------------  
  2. getDiffElementUseMap run time:471017640  
  3. The number of diff element is: 133332  

可见当数据量达到100000时（增大10倍），方法二仍然可以工作，而且时间也随着数据量增大线性增加。

而方法1很久也没有运行出来结果…

由此可见，利用HashMap的方法速度更快，能够满足基本要求。不知道大家还有哪些想法可以交流交流。希望对大家有帮助。

PS：如果用C++ STL实现的话，运行速度将更快！没事的时候再试试~~

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/u0mo5/p/4168479.html