如何查找两个系列是否相交？

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

2013-07-01 Srivathsan

循环是你的答案或移动问题：http://mathoverflow.net/ – Drakoumel

是序列总是排序，像在这个例子中？ – Joni

@Joni那些不是序列，而是**系列**（假设OP的措辞是正确的）[（this）]（http://en.wikipedia.org/wiki/Series_（数学）），所以是的。 – 2013-07-01 10:53:39

决策

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-02 08:00:38

更聪明，更短的算法。谢谢:) – Srivathsan

在Python中，你可以检查在一个序列发生在另一：

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

它的工作原理是从SEQ1的字符串表示去掉[]的，然后看是否在SEQ2它发生：

>>> str([1,2,3]) 
'[1, 2, 3]' 
>>> str([1,2,3,4]) 
'[1, 2, 3, 4]'

来源

2013-07-01 10:57:04 HennyH

这将有助于知道这是什么语言（不是说我认为OP正在寻找一种语言特定的功能）。另外，不只是'[1：]'工作？ – Dukeling

只有在数字连续时才有效。然后你必须以两种方式进行测试。 –

正如我看到你有2个独特的已排序列表。这个想法是在同一个循环中抛出两个排序的列表/数组并比较这些元素。迭代只会增加非匹配大小写索引中的一个索引，如果匹配则跳过两个索引。 Algorythm约为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-01 11:01:54 kikudjiro

这就是我要写的！ +1 –

为什么在'for'条件中使用'OR'而不是'AND'？这使你能够去除丑陋的'break'。 – Novak

for语句中的条件意味着仅当两个系列迭代完成时才会停止，而不附加其他条件。另一方面，身体中的这些突破有更多的条件可以在更具体的情况下停止。 – kikudjiro

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）
您可以使用hashset （见下文）： 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

并得出结论，如果列表都分类和连续，可以断定他们是否交叉或不很容易通过比较边界（见哈立德一个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-02 07:14:10

如何查找两个系列是否相交？

回答

相关问题