有ListString list1和ListString list2,两个集合各有上万个元素，怎样高效取出两个集合中不同的元素?
如题：要实现高效的遍历list，那么通过map实现为最佳算法，以下是实现思路：
* 1、用map存放list1和list2的所有元素，key为2个list的元素，value为元素出现的次数
* 2、在遍历2个list时，如果有相同的元素，则value++，如果没有，则直接添加到no_list
* 3、最后遍历map，取出value为1的元素，添加到no_list
代码如下：
1 public class Main { 2 3 /** 4 * @param args 5 */ 6 public static void main(String[] args) { 7 List<String> list1=new ArrayList<String>(); 8 List<String> list2=new ArrayList<String>(); 9 10 for(int i=0;i<10000;i++){11 list1.add(i+"test");12 list2.add(i*2+"test");13 }14 15 getNoList(list1,list2);16 }17 18 private static List<String> getNoList(List<String> list1,List<String> list2){19 long begin=System.currentTimeMillis();20 List<String> no_list=new ArrayList<String>();21 22 /**23 * 实现思路：24 * 1、用map存放list1和list2的所有元素，key为2个list的元素，value为元素出现的次数25 * 2、在遍历2个list时，如果有相同的元素，则value++，如果没有，则直接添加到no_list26 * 3、最后遍历map，取出value为1的元素，添加到no_list27 */28 Map<String,Integer> map=new HashMap<String, Integer>(); 29 List<String> max_list=list2;30 List<String> min_list=list1;31 32 if(list1.size()>list2.size()){33 max_list=list1;34 min_list=list2;35 }36 37 /**38 * 再进行2个list遍历时，优先遍历size最长的list，提高性能39 */40 for(int i=0;i<max_list.size();i++){41 map.put(max_list.get(i), 1);42 }43 44 for(int i=0;i<min_list.size();i++){45 String key_str=min_list.get(i);46 Integer count=map.get(key_str);47 if(count!=null){48 map.put(key_str, count++);49 continue;50 }51 /**52 * 这步很重要，在遍历第2个list时，由于第1个list已经遍历完毕，故在count为null时53 * 说明该元素为2个list的不同元素，可直接添加到no_list,大大提高性能54 */55 no_list.add(key_str);56 }57 58 for(Map.Entry<String, Integer> entry:map.entrySet()){59 if(entry.getValue()==1){60 no_list.add(entry.getKey());61 }62 }63 64 long end=System.currentTimeMillis();65 System.out.println("总共用时："+(end-begin)+"毫秒");66 //总共用时：56毫秒67 return no_list;68 }69 70 }TAG:
