6

これを行う 1 つの方法を次に示します。 O(m+n)wheremとnare は 2 つの配列の長さです。

import random

def comm_seq(arr_1, arr_2):
    if len(arr_1) == 0 or len(arr_2) == 0:
        return []

    m = len(arr_1) - 1
    n = len(arr_2) - 1

    if arr_1[m] == arr_2[n]:
        return comm_seq(arr_1[:-1], arr_2[:-1]) + [arr_1[m]]

    elif arr_1[m] < arr_2[n]:
        return comm_seq(arr_1, arr_2[:-1])

    elif arr_1[m] > arr_2[n]:
        return comm_seq(arr_1[:-1], arr_2)


if __name__ == "__main__":
    arr_1 = [random.randrange(0,5) for _ in xrange(10)]
    arr_2 = [random.randrange(0,5) for _ in xrange(10)]
    arr_1.sort()
    arr_2.sort()
    print comm_seq(arr_1, arr_2)

場合によっては比較未満を使用する手法はありO(m+n)ますか? 例:arr_1=[1,2,2,2,2,2,2,2,2,2,2,100]とarr_2=[1,3,100]

（ハッシュテーブルの実装を探していません）

4

4 に答える 4

5

二分探索アルゴリズムではO(logm)、長さ m の配列で数値を見つけるのに時間がかかります。したがって、長さ m の配列から長さ n の配列の各番号を検索すると、全体の時間計算量は になりO(nlogm)ます。m が n よりはるかに大きい場合、O(nlogm)は実際には 未満ですO(m+n)。したがって、このような状況では、二分探索に基づく新しいより優れたソリューションを実装できます。ソース

ただし、これは必ずしもバイナリ検索が O(m+n) の場合よりも優れていることを意味するわけではありません。実際、二分探索アプローチは、n << m (n は m に比べて非常に小さい) の場合にのみ優れています。

于 2012-11-22T04:08:39.717 に答える
5

私の知る限り、この問題を解決するにはいくつかの方法がありますが、どれも O(m + n) より優れたものではありません。両方の配列のすべての要素を比較する必要があるか、重複を見逃す可能性があるため、それよりも高速なアルゴリズムを作成する方法がわかりません(奇妙な量子コンピューティングの回答を除く)。

ブルート フォース ネストされた 2 つの for ループを使用します。最初の配列からすべての要素を取得し、2 番目の配列で線形検索します。O(M*N) 時間、O(1) 空間

Map Lookup ハッシュテーブルや二分探索木のようなルックアップ構造を使用します。最初の配列のすべてをマップ構造に入れ、2 番目の配列のすべてをループして、マップ内の各要素を調べて、それが存在するかどうかを確認します。これは、配列がソートされているかどうかに関係なく機能します。O(M*log(M) + N*log(M)) バイナリ検索ツリー時間または O(M + N) ハッシュテーブル時間、どちらも O(M) 空間です。

二分検索 ブルート フォースと同様ですが、最初の配列からすべての要素を取得し、2 番目の配列で二分検索します。 O(m*log(N)) 時間、O(1) 空間

Parallel Walk マージソートのマージ部分と同様。各配列の先頭から 2 つのポインターを開始します。2 つの要素を比較し、等しい場合は重複を格納し、そうでない場合はポインターを小さい方の値に 1 つ進め、配列の 1 つの末尾に到達するまで繰り返します。O(M + N) 時間、O(1) 空間

とにかく、両方の配列のすべての要素を調べる必要があります。そうしないと、すべての重複が見つかったかどうかわかりません。1 つの配列がはるかに大きいか、またははるかに小さいというフリンジ ケースを主張することはできますが、すべての範囲の入力を考慮しているアルゴリズムには当てはまりません。

于 2012-11-22T04:23:52.790 に答える
1

hash_table を使用して大きな配列を保存し、他の小さな配列をスキャンして 2 つの配列の交点を計算できます。

import random

def comm_seq(arr_1, arr_2):
    if len(arr_1) < len(arr_2): arr_1, arr_2 = arr_2, arr_1
    cnt = {}
    for item in arr_1: 
        cnt.setdefault(item, 0)
        cnt[item] += 1
    # save the large array in a hash_table
    ret = []
    for item in arr_2:
        p = cnt.get(item, 0)
        if p: 
            ret.append(item):
            cnt[item] -= 1
    # scan the small array and get the answer
    return ret

if __name__ == "__main__":
    arr_1 = [random.randrange(0,5) for _ in xrange(10)]
    arr_2 = [random.randrange(0,5) for _ in xrange(10)]
    arr_1.sort()
    arr_2.sort()
    print comm_seq(arr_1, arr_2)

O(1) として動作する py 辞書の複雑さを考慮すると、合計の複雑さは O(min(n, m)) です。

于 2012-11-22T04:19:05.470 に答える
1

片側二分探索と通常の二分探索を組み合わせて使用​​すれば、O(N*log(M/N)) 比較のアルゴリズムが可能です。最悪の場合 (両方の配列が同じサイズの場合)、これは O(N) = O(M + N) 回の比較に等しくなります。ここで、M は最大の配列のサイズ、N は小さい配列内の個別の要素の数です。

2 つの配列のうち最小のものを取得し、2 番目の配列でその各要素を検索します。片側二分探索から始めます。必要以上に大きな要素が見つかるまで、位置 M/N、2*M/N、4*M/N、... を試します。次に、通常のバイナリ検索を使用して、位置 0 と 2 k *M/N の間の要素を見つけます。

一致する要素が見つかった場合は、片側二分探索と通常の二分探索の同じ組み合わせを使用して、重複する一致する要素の実行が終了する場所を見つけ、適切な数の一致する要素を出力にコピーします。バイナリ検索の同じ組み合わせを使用して、より小さい配列内の重複要素の数をカウントし、これらの重複カウントの最小値を取得して、結果に含まれる要素の数を決定できます。

小さい配列の次の要素を続行するには、前のステップが終了した大きい配列の開始位置を使用します。

于 2012-11-22T08:44:42.400 に答える