arrays - 配列を効率的に処理する

Question

次の配列があるとしましょう。

配列 1: 都市のリスト (配列 2 と同じエントリが含まれる場合があります) 配列 2: 都市のリスト

次のlistSを出力したい：

1. 配列 1 のみの都市のリスト
2. 配列 2 のみの都市のリスト
3. 両方の配列の都市のリスト

1-3 を達成するための最も効率的な方法は何ですか?

各配列に都市の名前を格納し、foreach を実行して 2 つを比較することを考えていました。

Answer 1

配列がソートされている場合は、それらを並行してトラバースできます。

index_1 = 0 // assuming zero based indexing
index_2 = 0

repeat the follwoing loop:
if( index_0 is out of range )
  count (remaining) cities from array 2
else if( index_1 is out of range )
  count (remaining) cities from array 2
else {
a = get city from array 1 with the index_1
b = get city from array 2 with the index_2
if( a = b ) {
  increment no. of cities in both arrays
  increment both indices
}
else if( a < b )
  count cities from array 1 until city from array 2 is b, update indices
else 
  count cities from array 2 until city from array 1 is a, update indices
}
end loop

これは、配列サイズの線形時間でジョブを実行する必要があります。

配列がソートされていない場合は、効率的なソート アルゴリズムでソートします。

配列が小さい場合は、ネストされたループでブルート フォース アプローチを使用してください。