如何获得两个数组之间的交集作为新数组？
在不同的情况下，我多次遇到这个问题。它对所有编程语言都是通用的，尽管我对C或Java很满意。
让我们考虑两个数组(或集合)：
char[] A = {'a', 'b', 'c', 'd'};
char[] B = {'c', 'd', 'e', 'f'};如何将两个数组之间的公共元素作为新数组获取？在本例中，数组A和B的交集为char[] c = {'c', 'd'}。
我希望避免一个数组在另一个数组中重复迭代，这会增加(A的长度乘以B的长度)的执行时间，这在大型数组的情况下太多了。
有没有办法在每个数组中执行一次遍历来获取公共元素？
回答 16
Stack Overflow用户
发布于 2012-11-07 21:32:48
因为在我看来这是一个字符串算法，所以我暂时假设不可能对这个序列进行排序(因此是字符串)，那么您可以使用Longest Common Sequence algorithm (LCS)
假设输入大小不变，则问题的复杂度为O(nxm)，(两个输入的长度)
Stack Overflow用户
发布于 2012-11-07 21:15:23
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)的。
为了避免额外的空间，您可以使用基于排序的方法。
Stack Overflow用户
发布于 2012-11-07 22:20:58
效率的下限是O(n) -您至少需要读取所有元素。然后有几个分配：
愚蠢而简单的方法
在数组二中搜索数组一中的每个元素。时间复杂度为O(n^2)。
排序方法
您只需要对数组一进行排序，然后使用二进制搜索从数组二中搜索元素。时间复杂度:排序O(nlogn)，搜索O(n * logn) = O(nlogn)，总O(nlogn)。
散列方法
从数组一的元素创建一个哈希表。从哈希表中的第二个表中搜索元素。时间复杂度取决于散列函数。在最好的情况下(所有元素都有不同的散列值)，搜索可以达到O(1)，但在最坏的情况下(所有元素都有相同的散列值)，可以达到O(n)。总时间复杂度: O(n^x)，其中x是散列函数效率的因子(介于1和2之间)。
一些散列函数可以保证构建一个没有冲突的表。但是，对于每个元素，构建不再需要严格的O(1)时间。在大多数情况下，它将是O(1)，但如果表已满或遇到冲突，则需要重新散列该表-花费O(n)时间。这种情况发生的频率不是很高，比clean adds要少得多。因此，摊销时间复杂度为O(1)。我们不关心某些加法需要O(n)时间，只要大多数加法需要O(1)时间。
但即便如此，在极端情况下，每次插入都必须对表进行重新散列，因此严格的时间复杂度将为O(n^2)
https://stackoverflow.com/questions/13270491
复制相似问题