求两个整数数组的最长交集

Question

我有这个问题，但不知道从时间复杂度和空间复杂度的角度来看，解决它的最佳方法是什么。假设我有两个整数数组

   a={1,2,3,4,5}
   b={2,3,4,5,6}

，当然它们不一定要排序。

那么问题是如何找到2,3,4,5?最好有一些代码。提前感谢

Answer 1

为什么这里需要DP ?题目要求找出最长的交集，而不是任何交集。我错过了什么吗?

有很多方法可以解决这个问题。

int [] a = {...}; // n elements  
int [] b = {...}; // m elements  

可以将一个数组存储在字典中，另一个数组中的每个元素检查字典。那个O(n)。这将花费你更多的空间，因为字典。它不在位置

另一个解决方案是对于a中的每个元素，你可以对b进行线性搜索，也就是O(n.m)

如果对两个数组都进行排序，则

是另一个。然后对一个数组中的每个元素在另一个数组中进行二分搜索。你会找到两者的交点。这是mlogn + nlogn或nlogm + mlogm

我们这里真的需要DP吗?

Answer 2

这实际上是一个非常流行的编程问题。有一种动态规划方法可以解决这个问题。您可以在http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Answer 3

希望这个链接能解决你的问题。您必须编写一个公共函数，它将在两个数组中显示公共数字。而且它只使用一个for循环，这就是为什么它的复杂度将只是 0 (N)。

查找常用数字

代码用C编写。但是我希望你能理解其中的逻辑。

Answer 4

首先我们应该对数组进行排序，其次我们应该使用二分搜索来找到这些数组的交集。为什么?因为如果我们对搜索交集进行抽样，不进行排序，我们的算法劳动量将是N^2，但如果在搜索之前对数组进行排序，我们总共将有[log_2(N)N + ( N(log_2(N)) up to N^2 )]。我的方法对大多数样本都很有用