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

algorithm java c++ c

2022-08-31 13:44:59

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

让我们考虑两个数组（或集合）：

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

如何将两个数组之间的公共元素作为新数组获取？在本例中，数组 A 和 B 的交集为。char[] c = {'c', 'd'}

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

有没有办法在每个数组中执行一次传递来获取公共元素？

答案 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)

若要避免额外的空间，可以使用基于排序的方法。

答案 2

效率的下限是O（n） - 你至少需要读取所有元素。然后有几个apporaches：

愚蠢的最简单的方法

从数组 2 中的数组 1 中搜索每个元素。时间复杂度 O（n^2）。

排序方法

您只需要对数组一进行排序，然后使用二进制搜索从数组二中搜索元素。时间复杂度：排序 O（nlogn），搜索 O（n * logn） = O（nlogn），总 O（nlogn）。

哈希方法

从数组 1 元素创建哈希表。搜索哈希表中第二个表的元素。时间复杂度取决于哈希函数。在最优情况下（所有元素将具有不同的哈希值），您可以实现搜索的 O（1），但在最坏的情况下，您可以实现 O（n）（所有元素将具有相同的哈希值）。总时间复杂度：O（n^x），其中 x 是哈希函数效率的因子（介于 1 和 2 之间）。

某些哈希函数可以保证构建没有冲突的表。但是，对于每个元素，建筑物不再严格地花费O（1）时间。在大多数情况下，它将是 O（1），但是如果表已满或遇到冲突，则需要重新哈希表 - 占用 O（n）时间。这种情况并不经常发生，比干净的添加要少得多。因此，摊销时间复杂度为 O（1）。我们不关心一些加法需要O（n）时间，只要大多数加法需要O（1）时间。

但即便如此，在极端情况下，每次插入时都必须重新哈希表，因此严格的时间复杂度将为O（n^2）