java - 从两个数组中查找唯一项

Question

我想知道在从两个数组打印唯一项时，有什么更好的解决方案可以产生比 O(n^2) 更低的复杂性。有什么想法吗？

    int[] a = {1,2,4,5,8};
    int[] b = {3,2,5,7,8};

    ArrayList unMatch = new ArrayList() ;
    for(int i=0; i<a.length; i++){
        boolean contains = false;
        innerloop:
            for(int k =0; k<b.length; k++){
                if(a[i]==b[k]){
                    contains = true;
                    break innerloop;
                }
            }
        if(!contains){
            unMatch.add(a[i]);
        }

    }
    for(int i=0; i<b.length; i++){
        boolean contains = false;
        innerloop:
        for(int k =0; k<a.length; k++){
            if(b[i]==a[k]){
                contains = true;
                break innerloop;
            }
        }
        if(!contains){
            unMatch.add(b[i]);
        }
    }

Output: [1,4,3,7]

Answer 1

如果可以使用其他数据结构，我认为这种解决方案会更好:

首先我们将填写一个 HashMap<Integer, Integer>与项目及其频率:

public static Set<Entry<Integer, Integer>> fillMap(int[] a, int[] b) {
    HashMap<Integer, Integer> entries = new HashMap<>();    
    for (Integer i : a) 
        entries.put(i, entries.get(i) == null ? 1 : entries.get(i) + 1);

    for (Integer i : b) 
        entries.put(i, entries.get(i) == null ? 1 : entries.get(i) + 1);

    return entries.entrySet();
}

然后打印唯一项(值为 1 的项):

for (Entry<Integer, Integer> entry: fillMap(a, b)) 
    if (entry.getValue() == 1) 
        System.out.println("This value is unique: " + entry.getKey() );

如果我没记错的话，它应该在 O(n+m) 中运行(或者只是 O(n) 如果数组的长度始终相同)。