1

サイズの異なる 2 つの配列の共通要素を取得する最善の方法を見つけなければなりません。

配列は順不同です。共通要素は異なる位置にありますが、同じ順序 (配列 A で共通要素bがaの後に来る場合、配列 B でも同じことが起こります) で、最大距離 N です。

O(N) の追加スペースを使用することはできません。

実際には、配列 A から N 個の要素を抽出し、それらをマージソートで並べ替え、配列 B の N 個の要素を使用して 2 分探索を実行します。次に、見つかった一致の位置から次の N 個の要素を取得し、別のサイクルを実行します。

このコストは、配列 B の長さとしてmを使用すると、O(m N log N) になります。

ハッシュテーブルを使用してみましたが、衝突を管理するにはリストを実装する必要があり、効率が低下します。

より良い方法はありますか？

4

1 に答える 1

0

一致したシーケンスに「穴」があると仮定すると (A = [1,3,2] AND B = [1,4,2] の場合、MatchSet = {1,2})

たぶん私は間違っているかもしれませんが、この疑似コードを試すことができます:

i <- 0; j <- 0; jHit <- -1
matchSet <- Empty
While i < Length(A) AND j < Length(B):
    If A[i] == B[j] Then
        matchSet.add(A[i])
        i <- i+1
        jHit <- j
    End If
    j <- j+1
    If j == Length(B) Then
        i <- i+1
        j <- jHit+1
    End If
End Loop

最初のインデックス (i) は、B に見つからない A の次の要素を指しますが、(j) は B の次の要素 (A に見つかった最後の要素の後) を探すために使用されます。

これにより、O(mN) の時間計算量と O(N) のスペース使用量が得られます。

ここに Python での実装があります。

def match(A,B):
    i = 0
    j = 0
    jHit = -1
    res = []
    while i < len(A) and j < len(B):
        if A[i] == B[j]:
            res.append(A[i])
            i += 1
            jHit = j
        j += 1
        if j == len(B):
            i += 1
            j = jHit+1
    return res
于 2013-08-22T11:20:13.227 に答える