2

私は2つのソートされた配列を持っています。両方が異なるかどうかを確認する必要があります。

これらの配列には、特定の範囲内の要素があります。

複数の要素が異なる場合があります。

配列はさまざまなサイズを持つことができます。この場合、違いを指摘できるはずです

大まかな例:

入力：

array1: 1 2 4 5 8 9 12
array2: 1 4 8 10 12 13 14

ここでの範囲は 1 ～ 15 です。

最も最適な比較アルゴリズムは何ですか?

相違点と類似点も指摘できるはずです。たとえば、4 は両方にあり、2 番目の配列には 5 がありません。

私の解決策：

  1. 配列のインデックスを追跡するための 2 つのポインター。

  2. それらを配列の先頭に向けます。

  3. 最初の 2 つの要素の比較を開始します。

  4. 両方が等しい場合 -> 次のものに移動します。
    そうしないと

    1. 配列の 2 つの要素のうち最大のものを見つけます。array1 に大きな要素があるとします。

    2. もう一方の配列の要素を二分探索 (array2) --> その配列の要素の pos を pos と言う

    3. pos まで配列の要素を破棄します。

  5. ポインタをインクリメントします。このポインターまで配列のその部分を破棄します。繰り返す。

これには複雑さがありますn log n（平均よりもはるかに少ないです。これは、すべての要素を検索する必要がある場合です）。

4

7 に答える 7

1

完全にテストされていません（重複がある場合はうまく機能しません）：

var same = new List<int>();
var inAonly = new List<int>();
var inBonly = new List<int>();

int b = 0;
int a = 0;
//first look at all the elements until one of the lists run out of elements
for(; a < inputa.Count && b < inputb.Count;) {
     //if element is the same, then add to same
     //and the problem with duplicates is found here, if a contains two "1", but b only contains one, then same will report a single "1", but inAonly will also contain a "1"
     if (inputa[a] == inputb[b]){
       same.Add(inputa[a]);
       a++;
       b++;
     }
     //otherwise, we check if a < b, if that is the case, we know that a only exists in a, otherwise it must only exist in b.
     else if (inputa[a] < inputb[b])
     {
        inAonly.Add(inputa[a]);
        a++
     } else         {
        inBonly.Add(inputb[b]);
        b++
     }
}
//add the rest of the elements if one array is longer than the other
for(; a < inputa.Count;a++)
   inAonly.Add(inputa[a]);
for(; b < inputb.Count;b++)
   inBonly.Add(inputb[b]);
于 2013-08-21T08:40:48.430 に答える
0

配列がメモリのブロック (malloc で割り当てたもの) である場合、配列を 32 または 64 ビットの整数にキャストすることで比較を高速化できます。そうすれば、多数の配列要素を単一の == テストと比較できます。

また、配列に特定の数の要素があることを知っている場合は、ループを展開して、たとえば 8 if ステートメントの方が高速になります。比較を保存し、ループの各実行の最後にジャンプします。

于 2013-08-21T08:22:26.590 に答える
0

これにどのようにアプローチするかについては正しい軌道に乗っていますが、検索は必要ありません。(実際のアルゴリズムについては下部を参照)

先頭を指す 2 つのポインターから始めます。

        v
array1: 1 2 4 5 8 9 12

        v
array2: 1 4 8 10 12 13 14

（あなたが持っているように）要素が同じである場合は、それらを"In-Both"セットに追加し、両方のポインターをインクリメントして、次のようにします。

          v
array1: 1 2 4 5 8 9 12

          v
array2: 1 4 8 10 12 13 14

ここでさまざまな要素に出くわしました。ここで検索する代わりに、ポインターがある場所に 2 つの過去があるはずがないという事実を利用して、セットarray2に追加2します"Only_in_array1"。array1ポインタのみをインクリメントします。したがって、最終的には次のようになります。

            v
array1: 1 2 4 5 8 9 12

          v
array2: 1 4 8 10 12 13 14

最終的に一致するので、に 4 を追加し、"In-Both"両方のポインターをインクリメントします。

              v
array1: 1 2 4 5 8 9 12

            v
array2: 1 4 8 10 12 13 14

このパターンを続けると、最終的には次のようになります。

                     v
array1: 1 2 4 5 8 9 12

                  v
array2: 1 4 8 10 12 13 14

最初のポインターが配列から外れると、2 番目の (より長い) 配列の残りの要素が最初の配列にないことがわかります。

アルゴリズムを一般化するには:

  • 両方の配列の先頭にある 2 つのポインターから始めます (情報を保持したい初期化とデータ構造: 3 つのリスト/セットを使用しました)。

  • 3つのケースのうちの1つを持つことができます

    1. p1 の値が p2 と等しいin both: 値を配列に追加し、両方をインクリメントします。

    2. p1 の値が p2 より小さいonly in array1: p1 の値を配列に追加し、p1のみをインクリメントします

    3. p1 の値が p2 より大きいonly in array2: p2 の値を配列に追加し、p2のみをインクリメントします。

  • 配列の 1 つ (またはそのように発生した場合は両方) の終わりに到達するまで、これらの条件でループします。次に、他のリストの残りの項目をそれぞれのonly in arrayXリストに追加します。

このアルゴリズムは各項目に 1 回しかヒットしないため、O( n ) である必要があります。お役に立てれば

于 2013-08-21T13:28:39.120 に答える