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

问题描述

我在各种情况下多次遇到这个问题.尽管我对 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'}.

我想避免一个数组在另一个数组中的重复迭代将执行时间增加(A 的长度乘以 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(nxm)，(两个输入的长度)

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

这篇关于如何将两个数组之间的交集作为新数组?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！