如何获得两个数组之间的交集作为一个新的数组？ [英] How do I get the intersection between two arrays as a new array?

问题描述

我在各种情况下多次遇到这个问题。

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的长度为A的长度），这种情况太多了

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?

推荐答案

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem\">最长通用序列算法（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屋！