2

2,3,4,5,6 と 4,5,6,7,8,9 という 2 つのシリーズがあるとします。これらのシリーズにはいくつかの共通点があります。与えられた 2 つの系列が交差するかどうかを調べるコンピューター プログラムを作成するには、どのアルゴリズムを使用すればよいですか?

4

4 に答える 4

3

私がキャッチしたように、すでにソートされた2つの一意のリストがあります。アイデアは、ソートされたリスト/配列の両方を同じループでスローし、要素を比較することです。反復は、一致しない場合はインデックスの 1 つだけをインクリメントし、一致する場合は両方のインデックスをスキップします。アルゴリズムは約 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 に答える
0

OPの質問は、 2つのリストが交差するかどうかだけを知ることでした. 私の答えは、より一般的な2つのリスト間の共通の数値を示しますが、それを変更するには、ブール値とブレークを追加するだけで済みます。

まず、リストはソートされていると仮定しますが、番号は連続していない可能性があります:

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

リストがソートされていない場合、次の3 つの解決策があります。

  • 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 に答える