logo标签列表

高效的列表交集算法

algorithmlistset-intersection
83

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

3
这听起来像一道作业问题 - 是吗？ - Erik Forbes
34
实际上不行。我在工作中，需要在一个名为eviews的统计建模环境中进行编程。Eviews没有内置集合交集功能，并且也不支持递归。我需要一个快速算法，因为我的集合往往很大，程序需要经常运行。谢谢！ - David
4
每个列表中的数值都是唯一的吗？如果是，你可以将这些列表合并，对结果进行排序，然后查找重复项。 - Fabio Ceconello
1
通常集合中有多少个元素？（例如，是否值得尝试实现哈希，还是可以通过排序来解决 = O（nlogn）？） - Jason S
2
你要排序的数据类型是什么？有时候，数据的特性可以在设计算法时加以利用。 - AShelly
显示剩余3条评论
15个回答
47

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

这听起来不错，但我也不相信我有访问哈希算法的权限。你有什么建议吗？ - David
6
然后，可以：
  • 对list1进行排序（时间复杂度：n log n）
  • 对list2进行排序（时间复杂度：n log n）
  • 将这两个列表合并，并在同时迭代这两个已排序列表时检查相似的条目（线性时间）
 - Frank
3
我没有足够的积分在其他帖子中发表评论，但关于快速排序是递归的这一点：您可以在不使用递归的情况下实现它。例如，请参见此处：http://www.codeguru.com/forum/archive/index.php/t-333288.html - Frank
4
如果您可以访问数组，那么肯定可以构建自己的哈希表。构建一个合理的哈希函数通常相当简单。 - Keith Irwin
1
那么如果你有多个列表，如何处理呢？比如说，你有多个列表，想要对它们求交集。在我看来，方法仍然是：为第一个列表创建哈希表，然后开始迭代剩下的列表，并检查它们的每个元素是否存在于哈希表中。是这样吗？ - khan
显示剩余2条评论
27

您可能需要了解布隆过滤器。它们是位向量，能以概率性的方式回答一个元素是否为集合成员的问题。可通过简单的按位 AND 操作来实现集合交集。如果有大量的空交集，布隆过滤器可以帮助您快速消除这些情况。但是，您仍然需要采用这里提到的其他算法之一来计算实际的交集。

http://zh.wikipedia.org/wiki/布隆过滤器
这是一种迷人的方法，可以有效地确定两个大集合是否重叠。 - Rick Sladkey
10

如果没有哈希，你大概有两个选择：

  • 比较每个元素与其他元素。 O(n^2)
  • 另一种方法是先排序列表，然后迭代它们: O(n lg n) * 2 + 2 * O(n)
还有一个问题：如果可以为每个元素添加一个属性，在两个集合中的所有元素上将其重置为零，然后在其中一个集合中将其设置为1，最后扫描第二个集合找到具有属性设置为1的元素。这是O(n + m)，但并非总是可行的。 - Roman Starkov
也许可以通过O(log n)的二分查找来改进它？ - knight
6
只是提醒，O(n lg n) * 2 + O(n) * 2 和 O(n lg n) 是相同的。 - porglezomp
首先，对链表进行排序不是nlogn的，因为您没有O(1)访问权限，您需要将其移动到数组中。其次，您需要仅对一个列表进行排序，然后使用第一个列表的每个元素在其中执行二进制搜索。 - shinzou
7
从EViews功能列表中可以看出，它支持复杂合并和连接（如果这是DB术语中的“join”，它将计算交集）。现在请查阅您的文档 :-)
此外，EViews还有自己的用户论坛 - 为什么不在那里提问呢？
6

使用集合1构建一个二叉搜索树，时间复杂度为O(log n)，然后迭代集合2并在二叉搜索树中搜索，时间复杂度为BST m X O(log n)，因此总时间复杂度为O(log n) + O(m)+O(log n) ==> O(log n)(m+1)

2
对于二叉搜索树部分，仍然需要对其中一个列表进行排序（这将会增加O(m log m)或者O(n log n)的复杂度）。尽管如此，这仍然是一个非常有用的答案：在我这种情况下，我有两个包含相同对象的列表，但是每个列表按照不同的对象属性进行排序——我需要知道哪些对象在这两个列表中都存在。这个答案并不关心每个列表按照哪个属性进行了排序。谢谢！ - accidental_PhD
2
实际上，构建树的时间复杂度是O(n log n)，因此总时间复杂度为O((n+m)log n)。 - c-urchin
6

在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;
}
3
这是我想到的另一个可能的解决方案，时间复杂度为O（nlogn），没有任何额外的存储。您可以在此处查看https://gist.github.com/4455373。
它的工作原理如下：假设集合不包含任何重复项，请将所有集合合并成一个并进行排序。然后循环遍历合并的集合，并在每次迭代时创建当前索引i和i + n之间的子集，其中n是宇宙中可用的集合数。我们在循环时寻找大小为n的重复序列，与宇宙中的集合数相等。
如果i处的子集等于n处的子集，则意味着i处的元素重复了n次，这等于总集合数。由于任何集合中都没有重复项，因此每个集合都包含该值，因此我们将其添加到交集中。然后，我们通过i +其余部分和n之间的移动索引来移动索引，因为肯定不会有任何这些索引形成重复序列。
对于链表来说，排序的时间复杂度不可能达到nlogn。 - shinzou
2
2

首先，使用快速排序算法对两个列表进行排序：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是列表的大小。

编辑：正如评论中所说，快速排序是递归的，但似乎也有非递归的实现方法。（链接）（链接）

快速排序不是递归的吗？还是有非递归版本的吗？ - David
我不会称之为O(max(n,m))。你还进行了两次排序。 - Tom Ritter
有没有非递归版本的归并排序也能够工作？ - David
1
有一种非递归快速排序。将要排序的完整区间推入堆栈。然后在循环中，弹出并分割该区间。需要进一步排序的任何区间都会被推入堆栈。回到循环顶部，弹出分割...反复执行，直到堆栈为空。 - EvilTeach
这里有一个小问题：快速排序并不能保证在O(n log n)的时间内运行。实际上，在最坏情况下，它是一个Omega(n^2)算法。我们只能说快速排序所需的平均时间是O(n log n)。 - rbrito
显示剩余3条评论
1
我赞同“集合”这个想法。在JavaScript中，您可以使用第一个列表来填充一个对象，使用列表元素作为名称。然后，您可以使用第二个列表中的列表元素，并查看这些属性是否存在。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接