从两个数组中找到独特的项

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]);
        }
    }

输出：[1,4,3,7]

- Atif Imran

---

你可以通过先对数组进行排序，以 O(n log n) 的时间复杂度完成它。 - Andy Turner

当然，那是第一件事。谢谢。 - Atif Imran

你能做到的最快速度是 *O(n+m)*，因为无论如何你都必须遍历两个数组中的项。 - Idos

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)）范围内运行。

- Idos

---

这是我写的代码... 不管怎样，它是线性的，如果数组大小相同，则为 *O(n+n)=O(2n)=O(n)*。 - Idos

Answer 2

将数组转换为数组列表

List<Integer> c = Array.asList(a);
List<Integer> d = Array.asList<b>;
c.removeAll(d);
c.addAll(d);
c.froEach(System.out::println);

我用Java使用lambda表达式完成了这个，时间复杂度只有O(n)

希望这段代码能回答你的问题

- SmashCode

Answer 3

使用Set可以降低复杂度。Set不允许重复元素。Set可以分为以下几种：

1. HashSet - HashSet是使用哈希表实现的，元素没有顺序。 add、remove和contains方法的时间复杂度为O(1)。
2. LinkedHashSet - 使用树（RB-Tree），元素没有顺序。相同方法的复杂度为O(log n)。
3. TreeSet - 使用哈希表和链表，元素有顺序。相同方法的时间复杂度为O(1)。

例如：

    HashSet<Integer> set = new HashSet<>();
    for(int n : a) {
        set.add(n);
    }
    for (int n : b) {
        set.add(n);
    }

因此，它在这里提供了线性顺序 - O（n + m）。

- karzler007