2

考虑到我有两个系列 2,3,4,5,6 和 4,5,6,7,8,9。这些系列中有几个共同点。我应该使用什么算法来编写计算机程序来查找两个给定系列是否相交。

4

4 回答 4

3

当我发现你有 2 个独特的已排序列表。这个想法是在同一个循环中抛出两个排序列表/数组并比较元素。在不匹配的情况下，迭代将仅增加一个索引，如果匹配则跳过两个索引。算法大约是 O(N+M)，其中 N 和 M 是 2 个数组的大小。这是 JavaScript 中的示例：

var l1 = [2,3,4,5,6];
var l2 = [4,5,6,7,8,9];
var intersection = [];
for (var i1=0,i2=0; i1<l1.length || i2<l2.length;) {
    if (l1[i1] == l2[i2]) {
        intersection.push(l1[i1]);
        ++i1;
        ++i2;
    } else {
        if (l1[i1] < l2[i2]) {
            ++i1;
            if (i1 >= l1.length)
                break;
        } else {
            ++i2;
            if (i2 >= l2.length)
                break;
        }
    }
}
console.log(intersection);
于 2013-07-01T11:01:54.917 回答
2

决定

IF (A.START >= B.START AND A.START <= B.END)
OR (A.END >= B.START AND A.END <= B.END)
OR (B.START >= A.START AND B.START <= A.END)
OR (B.END >= A.START AND B.END <= A.END)

例子

A = { 2,3,4,5,6 }
B = { 4,5,6,7,8,9 }

A.START = 2
A.END = 6

B.START = 4
B.END = 9

(A.END >= B.START AND A.END <= B.END)
6 >= 4 AND 6 <= 9 ~ TRUE
于 2013-07-02T08:00:38.643 回答
1

在 Python 中，您可以检查一个序列是否出现在另一个序列中：

>>> str(seq1)[1:-1] in str(seq2)

它的工作原理是[]从 seq1 的字符串表示中删除 's，然后查看它是否出现在 seq2 中：

>>> str([1,2,3])
'[1, 2, 3]'
>>> str([1,2,3,4])
'[1, 2, 3, 4]'
于 2013-07-01T10:57:04.860 回答
0

OP 的问题是只知道两个列表是否相交。我的答案给出了两个列表之间更通用的通用数字，但它只需要添加一个布尔值和一个中断来改变它。

首先，我假设列表已排序，但数字不能连续：

C中的解决方案：

#include <stdio.h>

int main() {
    int l1[] = {2, 3, 4, 5, 6};
    int l2[] = {4, 5, 6, 7, 8, 9};

    int i1 = 0;
    int i2 = 0;

    while (i1 < 5 && i2 < 6) {
        if (l1[i1] == l2[i2]) {
            printf("%d\n", l1[i1]);
            i1++;
            i2++;
        } else if (l1[i1] < l2[i2]) {
            i1++;
        } else {
            i2++;
        }
    }

    return 0;
}

已验证：

 % ./a.out 
4
5
6

Python中的解决方案：

l1 = [2, 3, 4, 5, 6]
l2 = [4, 5, 6, 7, 8, 9]
i1 = 0
i2 = 0

while i1 < len(l1) and i2 < len(l2):
    if l1[i1] == l2[i2]:
        print(l1[i1])
        i1 += 1
        i2 += 1
    elif l1[i1] < l2[i2]:
        i1 += 1
    else:
        i2 += 1

现在，如果列表未排序，您有三个解决方案：

  • 您可以遍历 2 个列表并检查两个元素何时相同：O(n*m)
  • 您可以先对它们进行排序以使用第一个算法：O(n log n) + O(m log m) + O(n+m)
  • 您使用哈希集（见下文）：O(n+m)

看：

l1 = [5, 6, 4, 2, 3]
l2 = [8, 6, 5, 7, 4, 9]
i1 = 0
i2 = 0

s1 = set(l1)

for v in l2:
    if v in s1:
        print(v)

可以说该集合不是强制性的，因为我可以直接编写v in l1，但是使用列表它将是第一个解决方案（in时间是线性的），而使用集合in应该几乎是时间常数。这对于大型列表可能很有用。

也验证了：

 % python inter.py 
6
5
4

最后，如果列表既是排序的又是连续的，您可以通过比较边界很容易地判断它们是否相交（参见 Khaled A Khunaifer 的回答：https ://stackoverflow.com/a/17420402/1787973 ）：

在 Python 中：

(l1[0] >= l2[0] and l1[0] <= l2[-1]
or l1[-1] >= l2[0] and l1[-1] <= l2[-1]
or l2[0] >= l1[0] and l2[0] <= l1[-1]
or l2[-1] >= l1[0] and l2[-1] <= l1[-1])
于 2013-07-02T07:14:10.030 回答