algorithm - 2つの配列ですべての重複を見つけるアルゴリズム

Question

2つのアレイですべての重複を見つけるための最良のアルゴリズムは何ですか？

私が考えることができるのは、ブルートフォースアルゴリズムです。

2つの配列を直接比較し、同じ番号が見つかったら、それを補助配列に格納します。しかし、時間計算量はO（n ²）です。

Answer 1

• 最初の配列の数値をハッシュ構造 (ハッシュセット) に追加します
• 2 番目の配列の各数値について、ハッシュセットの場合は最後の配列に追加し、そうでない場合は無視します

それは O(n+m) (配列のサイズ) になります。

Answer 2

O(n log n) アルゴリズムがあります。

Sort arr1 and arr2 using quick sort or merge sort

i = 0
j = 0
found = 0
while i < arr1.length and j < arr2.length:
      if (arr1[i] == arr2[j])
          found = found + 1
          i = i + 1
          j = j + 1
      else if (arr1[i] < arr2[j])
          i = i + 1
      else
          j = j + 1

Answer 3

配列を並べ替えてから、両方の配列を同時に調べ、現在の要素が他の要素よりも小さい場合は常に配列を進めます。複雑さ: O(nlogn)

Answer 4

配列内の重複を O(n) 時間で識別できます。このアプローチでは、ハッシュマップ、heres 疑似コードを使用します。

// a and b are input arrays
HashMap h
for e in a:
    if h[e] == 0:
        h[e]++
for e in b:
    if h[e] != 0:
        h[e]++
for e in h:
    if e > 1:
        print "Duplicate" + e

Hashmap[Element]はシンタックス シュガーであり、次のことを意味します。

キー e を持つ要素を取得し、存在しない場合は初期化子 0 で作成します