寻找两个整数数组的最长交集

Question

我有一个问题，但不知道在时间复杂度和空间复杂度方面怎样解决它。假设我有两个整数数组。

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

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

那么问题来了，如何找到2、3、4、5？最好附带一些代码。谢谢。

- user899628

---

确实最好有一些代码！ - Kerrek SB

请问您能否详细说明一下，如果数组未排序，应该找到什么？它应该返回最长的已排序交集吗？ - user545680

请编辑您的问题并在文本中提供清晰的问题陈述和/或包含更多示例，以及答案；例如，对于a={1,2,3,4,5}，b={2,3,1,4,5,6}，以及a={1,3,7,5,13,13}，b={2,13,7,1,4,5,13}。 - James Waldby - jwpat7

类似于@jwpat7的请求：请详细说明。例如，如果a = {1, 2, 3, 4, 5, 6, 7}和b = {1, 3, 4, 5, 8}，那么您期望的结果是{1, 3, 4, 5}还是{3, 4, 5}？第一个是最长公共子序列问题，第二个是最长公共子串问题。每个问题都有众所周知的解决方案。 - Mac

Answer 1

我们为什么需要动态规划(DP)呢？问题要求找到最长的交集，而不是任意的交集。我是否漏掉了什么关键点？

有很多解决方案。

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

你可以在字典中存储一个数组，并对另一个数组中的每个元素检查字典。这样是O(n)。由于使用了字典，这将占用更多的空间，并且不是原地操作。

另一种解决方案是对于a中的每个元素，在b上进行线性搜索。这是O(n.m)。

还有一种方法是，如果你对这两个数组进行排序，那么对于一个数组中的每个元素，在另一个数组中进行二分搜索。你将找到两个数组的交集。这将是mlogn + nlogn或nlogm + mlogm。 我们真的需要DP吗？

- DarthVader

Answer 2

这实际上是一个相当流行的编程问题。有一种动态规划方法来解决它。您可以在http://en.wikipedia.org/wiki/Longest_common_subsequence_problem了解更多相关信息。

- jeff

Answer 3

我希望这个链接能解决你的问题。 你需要编写一个通用函数，它将显示两个数组中的共同数字。 并且它只使用一个for循环。因此它的复杂度只有O(N)。

查找共同数字。

代码是用C语言编写的。但我希望你可以理解这个逻辑。

- vikiiii

Answer 4

首先，我们应该对数组进行排序，其次，我们应该使用二分查找来找到这些数组的交集。 为什么？因为如果我们在不排序的情况下简单地搜索交集，我们的算法复杂度将是N^2，但如果我们在搜索之前对数组进行排序，总体上我们将拥有[log_2(N)N + ( N(log_2(N)) up to N^2 )]。 我的方法对大多数样本都很有用。

- Pavel