找出List集合中不同的元素的方法

妖狐艹你老母 2022-08-08 19:54 181阅读 0赞

这几天在写代码时候用到了关于ArrayList的一些算法，在这里整理一下。有点小感悟：现在逐渐明白为什么大公司对算法的要求这么高，在写代码逻辑的时候就是用算法处理，而算法的效率的高低直接决定了你程序的运行性能，看来在以后的训练中药加强对算法的训练呀。

首先看一下CollectionUtils这个Collection工具类对list的一些处理，摘了别人的代码，把运行结果贴出来：

package com.web.test;
    
    import java.util.ArrayList;
    import java.util.Collection;
    import java.util.Collections;
    import java.util.List;
    
    import org.apache.commons.collections.CollectionUtils;
    import org.apache.commons.lang.ArrayUtils;
    
    public class CollectionUtilsTest {
    
        @SuppressWarnings("unchecked")
        public static void main(String[] args) {
    
            List<String> aList = new ArrayList<String>();
            aList.add("aaa");
            aList.add("bbb");
            aList.add("ccc");
            List<String> bList = new ArrayList<String>();
            bList.add("aaa");
            bList.add("ddd");
            bList.add("eee");
            // 并集
            Collection<String> unionList = CollectionUtils.union(aList, bList);
            // 交集
            Collection<String> intersectionList = CollectionUtils.intersection(aList, bList);
            // 是否存在交集
            boolean isContained = CollectionUtils.containsAny(aList, bList);
            // 交集的补集
            Collection<String> disjunctionList = CollectionUtils.disjunction(aList, bList);
            // 集合相减
            Collection<String> subtractList = CollectionUtils.subtract(aList, bList);
            // 排序
            Collections.sort((List<String>) unionList);
            Collections.sort((List<String>) intersectionList);
            Collections.sort((List<String>) disjunctionList);
            Collections.sort((List<String>) subtractList);
    
            // 测试
            System.out.println("A: " + ArrayUtils.toString(aList.toArray()));
            System.out.println("B: " + ArrayUtils.toString(bList.toArray()));
            System.out.println("A has one of B? : " + isContained);
            System.out.println("Union(A, B): " + ArrayUtils.toString(unionList.toArray()));
            System.out.println("Intersection(A, B): "+ ArrayUtils.toString(intersectionList.toArray()));
            System.out.println("Disjunction(A, B): " + ArrayUtils.toString(disjunctionList.toArray()));
            System.out.println("Subtract(A, B): "+ ArrayUtils.toString(subtractList.toArray()));
    
        }
    }

结果：

![Center][]

现在看一下他的源码实现：

首先是union：

public static Collection union(final Collection a, final Collection b) {
             ArrayList list = new ArrayList();
             Map mapa = getCardinalityMap(a);
             Map mapb = getCardinalityMap(b);
             Set elts = new HashSet(a);
             elts.addAll(b);
             Iterator it = elts.iterator();
             while(it.hasNext()) {
                 Object obj = it.next();
                 for(int i=0,m=Math.max(getFreq(obj,mapa),getFreq(obj,mapb));i<m;i++) {
                     list.add(obj);
                 }
             }
             return list;
         }

可以看出这里使用了set和map进行处理。

再是intersection：

public static Collection intersection(final Collection a, final Collection b) {
             ArrayList list = new ArrayList();
             Map mapa = getCardinalityMap(a);
             Map mapb = getCardinalityMap(b);
             Set elts = new HashSet(a);
             elts.addAll(b);
             Iterator it = elts.iterator();
            while(it.hasNext()) {
                Object obj = it.next();
                for(int i=0,m=Math.min(getFreq(obj,mapa),getFreq(obj,mapb));i<m;i++) {
                    list.add(obj);
                }
            }
            return list;
        }

对于交集的处理同样也是基于set和map的。关于其他实现，大家可以参照[源码][Link 1]，从上边这两段代码来看，效率并不高毕竟它是相当于遍历两个list，时间复杂度应该是n\*n。需要说明的是这些方法都是数学的集合算法。

对于比较两个链表可以在ArrayList中处理，也可以在HashMap中处理，现在给出这两中处理方式：

import java.util.Collection;
    import java.util.ArrayList;
    import java.util.Arrays;
    
    public class Repeated {
        public static void main( String  [] args ) {
            Collection listOne = new ArrayList(Arrays.asList("milan","dingo", "elpha", "hafil", "meat", "iga", "neeta.peeta"));
            Collection listTwo = new ArrayList(Arrays.asList("hafil", "iga", "binga", "mike", "dingo"));
    
            listOne.retainAll( listTwo );
            System.out.println( listOne );
        }
    }

这里用到的是retainAll函数，它的作用是两个集合求交集，只保留交集数据 ，在set中有个名字类似的函数交addAll(Collection c) ，它的作用是将c中所有元素添加到一个Set中，如果Set中已有某一元素，则不添加，因Set不允许有重复值。

再看一下HashMap的处理方式：

import java.util.Collection;
    import java.util.HashSet;
    import java.util.Arrays;
    
    class Repeated {
          public static void main( String  [] args ) {
    
              Collection<String> listOne = Arrays.asList("milan","iga","dingo","iga","elpha","iga");
              Collection<String> listTwo = Arrays.asList("hafil", "iga","dingo","dingo","dingo");
    
              Collection<String> similar = new HashSet<String>( listOne );
              Collection<String> different = new HashSet<String>();
              different.addAll( listOne );
              different.addAll( listTwo );
    		  
              similar.retainAll( listTwo );
              different.removeAll( similar );
    		  
              System.out.printf(listOne, listTwo, similar, different);
          }
    }

这就是利用了set集合中元素是不同的来处理这个问题的。

或者不用集合，自己直接对这两个list进行处理：

private static ArrayList<String> getSame(ArrayList<String> list1, ArrayList<String> list2){
    	    
    	    ArrayList<String> diff = new ArrayList<String>();
    	    for(String str:list1){
    	    	if(!list2.contains(str)) {
    	    		diff.add(str);
    	    	}
    	    }
    	    return diff;
    	 }

这里有一篇讲集合非常好的文章，大家可以参考一下[https://www3.ntu.edu.sg/home/ehchua/programming/java/J5c\_Collection.html][https_www3.ntu.edu.sg_home_ehchua_programming_java_J5c_Collection.html]

**关注我，获取400个的赚钱金点子，轻松开启程序员的副业生涯**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hb3llcWl1_size_16_color_FFFFFF_t_70][]

[Center]: /images/20220731/f2b88a63bf9d456796bb36f80eca53c7.png
[Link 1]: http://grepcode.com/file/repo1.maven.org/maven2/commons-collections/commons-collections/2.1.1/org/apache/commons/collections/CollectionUtils.java
[https_www3.ntu.edu.sg_home_ehchua_programming_java_J5c_Collection.html]: https://www3.ntu.edu.sg/home/ehchua/programming/java/J5c_Collection.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hb3llcWl1_size_16_color_FFFFFF_t_70]: /images/20220731/af33e1e3cfdf45d68b017f80f358bae1.png