在不同的情况下,我多次遇到这个问题。它对所有编程语言都是通用的,尽管我对C或Java很满意。
让我们考虑两个数组(或集合):
char[] A = {'a', 'b', 'c', 'd'};
char[] B = {'c', 'd', 'e', 'f'};
如何将两个数组之间的公共元素作为新数组获取?在本例中,数组A和B的交集为char[] c = {'c', 'd'}
。
我希望避免一个数组在另一个数组中重复迭代,这会增加(A的长度乘以B的长度)的执行时间,这在大型数组的情况下太多了。
有没有办法在每个数组中执行一次遍历来获取公共元素?
发布于 2012-11-07 21:32:48
因为在我看来这是一个字符串算法,所以我暂时假设不可能对这个序列进行排序(因此是字符串),那么您可以使用Longest Common Sequence algorithm (LCS)
假设输入大小不变,则问题的复杂度为O(nxm),(两个输入的长度)
发布于 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)
的。
为了避免额外的空间,您可以使用基于排序的方法。
发布于 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
复制相似问题