高效的列表交集算法

Question

高效的列表交集算法

algorithmlistset-intersection

83

给定两个列表（不一定排序），最有效的非递归算法是什么，用于查找这些列表的交集？
我不认为我可以访问哈希算法。

- David

3

这听起来像一道作业问题 - 是吗？ - Erik Forbes

34

实际上不行。我在工作中，需要在一个名为eviews的统计建模环境中进行编程。Eviews没有内置集合交集功能，并且也不支持递归。我需要一个快速算法，因为我的集合往往很大，程序需要经常运行。谢谢！ - David

4

每个列表中的数值都是唯一的吗？如果是，你可以将这些列表合并，对结果进行排序，然后查找重复项。 - Fabio Ceconello

1

通常集合中有多少个元素？（例如，是否值得尝试实现哈希，还是可以通过排序来解决 = O（nlogn）？） - Jason S

2

你要排序的数据类型是什么？有时候，数据的特性可以在设计算法时加以利用。 - AShelly

显示剩余3条评论

15个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Imran · Answer 1

为什么不自己实现一个简单的哈希表或哈希集？如果你的列表很大，避免nlogn交集是值得的。

由于你事先对数据有一定了解，应该能够选择一个好的哈希函数。

- Andrea Ambu · Answer 2

如果支持集合（如标题中所称）作为内置，则通常会有一个交集方法。

无论如何，正如某人所说，如果您已经对列表进行了排序，那么可以很容易地完成它（我不会发布代码，因为已经有人这样做了）。如果您不能使用递归，则没有问题。有快速排序非递归实现。

- minchaej · Answer 3

时间复杂度: O(n) 空间复杂度: O(1) 用于识别交点的解决方案。

例如，通过在每次到达末尾时交换指针，这两个给定节点将检测到交点。视频解释在此处。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode pA = headA;
    ListNode pB = headB;
    while (pA != pB) {
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    return pA;
}

谢谢。

编辑

我对交集的理解是找到交点。

例如：

对于给定的列表 A 和 B，A 和 B 将在点 c1 "相遇/交叉"，上述算法将返回 c1。正如 OP 所述，OP 没有访问哈希映射或某种类型，我相信 OP 是说该算法应具有 O(1) 空间复杂度。

我是从 Leetcode 上获得这个想法的，如果您感兴趣：两个链表的交点。

- Adelin · Answer 4

根据Big-Oh符号的定义：

如果存在正常数c和n 0 ，使得N ≥ n 0 时 T(N) ≤ cf(N)，则 T(N) = O(f(N))。

实际意义是，如果两个列表的大小相对较小，例如每个列表不超过100个元素，则使用两个for循环可以很好地解决问题。循环第一个列表并在第二个列表中查找相似的对象。在我的情况下，它可以很好地工作，因为我的列表中不会有超过10-20个元素。但是，一个好的解决方案是对第一个列表进行排序O(n log n)，对第二个列表也进行排序O(n log n)，然后将它们合并，大约需要O(n log n)的时间，粗略地说是O(3n log n)，假设两个列表的大小相同。

- · Answer 5

在PHP中，类似于

function intersect($X) { // X is an array of arrays; returns intersection of all the arrays
  $counts = Array(); $result = Array();
  foreach ($X AS $x) {
    foreach ($x AS $y) { $counts[$y]++; }
  }
  foreach ($counts AS $x => $count) {
    if ($count == count($X)) { $result[] = $x; }
  }
  return $result;
}