java - 如何将两个数组之间的交集作为新数组？

Question

我在各种情况下多次遇到这个问题。尽管我对 C 或 Java 很熟悉，但它对所有编程语言都是通用的。

让我们考虑两个数组(或集合):

char[] A = {'a', 'b', 'c', 'd'};
char[] B = {'c', 'd', 'e', 'f'};

如何将两个数组之间的共同元素作为一个新数组？在这种情况下，数组 A 和 B 的交集是 char[] c = {'c', 'd'}。

我想避免一个数组在另一个数组中的重复迭代，这将将执行时间增加(A 的长度乘 B 的长度)，这在大数组的情况下太多了。

有什么方法可以在每个数组中进行单次传递以获取公共(public)元素？

Answer 1

foreach element e in array A
    insert e into hash table H

foreach element e in array B
    if H contains e 
        print e

这个算法在时间上是O(N)，在空间上是O(N)。

为了避免多余的空间，您可以使用基于排序的方法。