algorithm - ソート済み配列の交点の修正

Question

この問題に遭遇しました-入力-2つのソートされた配列a1とa2が与えられました。2 番目の配列に存在しない要素を見つける必要があります。

私には2つのアプローチがあります

1) ハッシュテーブル - O(m+n)
[2 番目の配列が小さい場合に使用]

2) 二分探索 - O(m*logn)
[2 番目の配列が巨大な場合に使用]

より優れた時間の複雑さを持つ他のアプローチはありますか?

ありがとうございました

Answer 1

それらを並行して繰り返すだけです。

JavaScriptの例を次に示します。

var a1 = [1, 2, 3, 4, 5, 6, 7, 9];
var a2 = [0, 2, 4, 5, 8];

findNotPresent(a1, a2); // [1, 3, 6, 7, 9]


function findNotPresent(first, second) {
    var first_len = first.length;
    var first_index = 0;

    var second_len = second.length;
    var second_index = 0;

    var result = [];

    while (first_index < first_len && second_index < second_len) {
        if (first[first_index] < second[second_index]) {
            result.push(first[first_index]);
            ++first_index;
        }
        else if (first[first_index] > second[second_index]) {
            ++second_index;
        }
        else {
            ++first_index;
            ++second_index;
        }
    }

    while (first_index < first_len) {
        result.push(first[first_index++]);
    }

    return result;
}

O（max（N、M））がかかると思います。