一种求有序集交集的算法
一种求有序集交集的算法
提问于 2016-03-02 07:29:51
我一直在寻找找到两个有序集的交集的方法，这些交集比迭代方式更有效。最终，我找到了这个问题：intersection and union of n-arrays in C。然而，我不明白两个集合的交集如何等于两个子集的交集的交集。我想弄清楚如何用递归做分而治之的算法，但我不能理解给出的例子是如何工作的。
更具体地说，一个分而治之的算法如何在两个集合上工作，例如：
A = 1, 2, 3, 4
B = 3, 5, 6, 7这似乎不像一个分而治之的算法，实际上可以一致地在3处找到交叉点。
回答 2
Stack Overflow用户
发布于 2016-03-02 07:53:32
然而，我不明白两个集合的交集如何等于两个子集的交集的交集。
这不是你的链接所说的(因为这是错误的，正如你所认识到的)。
找到一个有序集合的交集，即。两个排序数组的公共元素，
在不迭代它们的情况下是不可能的。它不会比O(N)更好。
Stack Overflow用户
发布于 2016-03-02 14:22:33
在两个数组之间，找出最后一个元素大于另一个数组的第一个元素。
例如：
A = 1, 2, 3, 4
B = 3, 5, 6, 7选择阵列A。在A上从右到左应用二进制搜索，以查找满足以下条件的元素：
A[i] >= B[0]现在使用这两个数组的线性搜索：
A[i......n]
B[0......m]其中n和m分别是A和B的长度。
我认为它比第一次尝试的线性搜索的复杂度要低。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/35735699
复制相关文章
相似问题
腾讯云开发者
