algorithm - データ構造を使用せずに 2 つの集合の交点を見つけるアルゴリズム

Question

外部データ構造（ハッシュテーブルなど）を効率的に使用せずに、等しい要素（整数など）の2つの配列の交点を決定するアルゴリズムを知りたいです（O（nlogn））？

Answer 1

ソートし、イテレータを使用して各要素配列を反復処理します:

if A[iter1] > B[iter2]: increase iter2
else if A[iter1] < B[iter2]: increase iter1
else: element is in intersection, print and increase both iters

並べ替えはO(nlogn)、反復はO(n)、合計O(nlogn)

Answer 2

• 配列を並べ替える
• それらをループして一致を保存する

何かのようなもの...

var A = [0...N];
var B = [0...N];
var result = [];
Array.sort(A);
Array.Sort(B);
for(var x=0, y=0; x < N && y < N; x++) {
    while(A[x] < B[y] && y < N) {
        y++;
    }
    if(A[x] == B[y]) {
        result.push( B[y++] );
    }
}