algorithm - 高效的列表交集算法

Question

给定两个列表（不一定是排序的），找到这些列表的集合交集的最有效的非递归算法是什么？
我不相信我可以使用散列算法。

score 43 · Accepted Answer

您可以将第一个列表的所有元素放入一个哈希集中。然后，迭代第二个，并且对于它的每个元素，检查哈希以查看它是否存在于第一个列表中。如果是，则将其作为交集的元素输出。

score 26 · Accepted Answer

你可能想看看布隆过滤器。它们是位向量，可以给出一个元素是否是集合成员的概率答案。设置交集可以通过简单的按位与运算来实现。如果您有大量的空交点，布隆过滤器可以帮助您快速消除它们。但是，您仍然必须使用此处提到的其他算法之一来计算实际的交点。 http://en.wikipedia.org/wiki/Bloom_filter

score 10 · Accepted Answer

没有散列，我想你有两个选择：

天真的方法是将每个元素与其他元素进行比较。O(n^2)
另一种方法是先对列表进行排序，然后对其进行迭代： O(n lg n) * 2 + 2 * O(n)

score 7 · Accepted Answer

从eviews 功能列表看来，它支持复杂的合并和连接（如果这是数据库术语中的“连接”，它将计算交集）。现在浏览您的文档:-)

此外，eviews 有自己的用户论坛 - 为什么不在那里问_

score 6 · Accepted Answer

使用 set 1 构建二叉搜索树O(log n)并迭代 set2 并搜索BST m X O(log n)总O(log n) + O(m)+O(log n) ==> O(log n)(m+1)

score 6 · Accepted Answer

在 C++ 中，可以使用 STL map 尝试以下操作

vector<int> set_intersection(vector<int> s1, vector<int> s2){

    vector<int> ret;
    map<int, bool> store;
    for(int i=0; i < s1.size(); i++){

        store[s1[i]] = true;
    }
    for(int i=0; i < s2.size(); i++){

        if(store[s2[i]] == true) ret.push_back(s2[i]);

    }
    return ret;
}

score 3 · Accepted Answer

这是我想出的另一种可能的解决方案，时间复杂度为 O(nlogn)，并且没有任何额外的存储空间。你可以在这里查看https://gist.github.com/4455373

它是这样工作的：假设集合不包含任何重复，将所有集合合并为一个并对其进行排序。然后遍历合并的集合，并在每次迭代中在当前索引 i 和 i+n 之间创建一个子集，其中 n 是 Universe 中可用的集合数。我们在循环时寻找的是一个大小为 n 的重复序列，该序列等于宇宙中集合的数量。

如果 i 处的子集等于 n 处的子集，则意味着 i 处的元素重复 n 次，这等于集合的总数。由于在任何集合中都没有重复，这意味着每个集合都包含该值，因此我们将其添加到交集。然后我们将索引移动 i + 它和 n 之间剩余的内容，因为这些索引肯定不会形成重复序列。

score 2 · Accepted Answer

首先，使用 quicksort 对两个列表进行排序：O(n*log(n)。然后，通过首先浏览最低值来比较列表，然后添加公共值。例如，在 lua 中)：

function findIntersection(l1, l2)
    i, j = 1,1
    intersect = {}

    while i < #l1 and j < #l2 do
        if l1[i] == l2[i] then
            i, j = i + 1, j + 1
            table.insert(intersect, l1[i])
        else if l1[i] > l2[j] then
            l1, l2 = l2, l1
            i, j = j, i
        else
            i = i + 1
        end
    end

    return intersect
end

这是列表的O(max(n, m))位置n和m大小。

编辑：快速排序是递归的，如评论中所述，但看起来有非递归实现

score 2 · Accepted Answer

2

使用跳过指针和SSE 指令可以提高列表交集效率。

于 2016-06-16T14:11:25.140 回答

score 1 · Accepted Answer

为什么不实现自己的简单哈希表或哈希集？如果您的列表如您所说的那样大，那么避免 nlogn 交集是值得的。

由于您事先对数据有所了解，因此您应该能够选择一个好的散列函数。

score 1 · Accepted Answer

如果支持内置的集合（正如您在标题中所说的那样），通常会有一个交集方法。

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

score 1 · Accepted Answer

我支持“集合”的想法。在 JavaScript 中，您可以使用第一个列表来填充对象，使用列表元素作为名称。然后使用第二个列表中的列表元素并查看这些属性是否存在。

score 0 · Accepted Answer

在 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;
}

score 0 · Accepted Answer

时间：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 无法访问Hashmaps或某种方式，我相信 OP 是说算法应该具有O(1)空间复杂性。

前段时间我从 Leetcode 那里得到了这个想法，如果有兴趣的话：Intersection of Two Linked Lists。

score 0 · Accepted Answer

根据 Big-Oh 符号的定义：

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

这实际上意味着如果两个列表的大小相对较小，那么每两个 for 循环中少 100 个元素就可以了。循环第一个列表并在第二个列表中查找类似的对象。就我而言，它工作得很好，因为我的列表中最多不会有超过 10 - 20 个元素。但是，一个好的解决方案是对第一个 O(n log n) 进行排序，对第二个也进行 O(n log n) 排序并合并它们，另一个 O(n log n) 粗略地说 O(3 n log n)，说这两个列表大小相同。

algorithm - 高效的列表交集算法

15 回答 15

编辑

Related

Reference