找到两个阵列之间的交叉点的最好方法？ [英] Best way to find an intersection between two arrays?

问题描述

我在各种场合遇到这个问题很多次。这是通用于所有的编程语言，虽然我很舒服的C或Java。

I faced this problem many times during various situations. It is generic to all programming languages although I am comfortable with C or Java.

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

Let us consider two arrays (or collections):

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

我如何获得一个新的阵列的两个阵列之间的共同之处？ 在这种情况下，阵列A和B的交集是的char [] c = {'C'，'D'} 。

How do I get the common elements between the two arrays as a new array? In this case, the intersection of array A and B is char[] c = {'c', 'd'}.

我想避免一个阵列的反复迭代的其他数组，将内 通过（的时间长度B的长度），这是巨大的阵列的情况下，过多的增加的执行时间。

I want to avoid the repeated iteration of one array inside the other array which will increase the execution time by (length of A times length of B) which is too much in the case of huge arrays.

有没有什么办法，我们可以做一个单一的传球每个阵列中得到共同的元素？

Is there any way we could do a single pass in each array to get the common elements?

推荐答案

由于这在我看来就像一个字符串变换算法，我假设了一下，它不可能解决这序列（因此字符串），那么你可以使用最长公共序列算法（LCS）

Since this looks to me like a string algorithm, I'll assume for a moment that its not possible to sort this sequence (hence string) then you can use Longest Common Sequence algorithm (LCS)

假设输入的大小是恒定的，则问题有一个为O（n×m个），（两个输入长度）

Assuming the input size is constant, then the problem has a complexity of O(nxm), (length of the two inputs)

这篇关于找到两个阵列之间的交叉点的最好方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！