2つの配列の違いを見つける

Question

これは、既存の交差点/結合体の質問と重複していないようです（間違っているかもしれません）。

私は2つの値が含まれているクラスが含まれているのArrayList、例えば、

class A { 
    private int value; 

    public int getValue() { 
     return value; 
    } 
} 

そして、私のリストは

ArrayList<A> first, second; 

ある私はfirstとsecondから2つのインデックスを見つけたい、これを持っています最初のインデックスはの項目を指しており、それぞれの値はfirstであるが、secondではなく、secondのインデックスであり、respe値はsecondのみで、firstには含まれません。

例えば（データを有する中央行から読み出さ）：私は1 2と1 2 3 5の2つの指標を必要

hit     * * 
index of first 0 1 2 3 
---------------------------------- 
first.value  1 3 5 7 
second.value  1 2 4 6 7 8 
---------------------------------- 
index of second 0 1 2 3 4 5 
hit    * * * * 

。

注：

1. 私はサードパーティのライブラリを使用しない
2. 値は整数であり、ソートされた、と私はリターンの順序でもなければなりません。
3. firstとsecondの長さはどちらか一方が他方よりも長くなる可能性があります。

ありがとうございます。

PS：誰でも詳細を必要とする、これは私の問題の簡略化されたバージョンです。 firstは、実際にはサーバーのすべてのレコードであるSQLクエリのResultSetです。secondはローカルレコードのリスト（または別のローカルデータベースから処理されたものと見なされます）です。サーバー上のすべてのレコードを削除することです（first ）（second）に格納されていないレコードをリモートデータベースに追加します。ありがとう。

---

私の目標は、インクリメンタルリモートデータベース（MySQLの）に自分のローカルデータベース（SQLiteの）を転送することです@Tibrogarganするには。ローカルデータベースにはLocalIdというフィールド（重複はなくプライマリキーではありません）ともちろんその他のコンテンツ（〜10フィールド）があり、リモートデータベースへのコピー必須フィールド（〜5フィールド）とは別に、レコードがローカルデータベースから削除されているかどうかを確認します。他の要件として

、私はすでにリモート・データベースでLocalIdによって並べ替えられ、ローカルデータベースにLocalIdによって並べ替えArrayList、にすべてのローカルデータを読み込み、そしてrs経由ですべてのリモート・データへのアクセス権を持っています。

以前のバージョンのコードでは、ローカルデータベースで最後のLocalIdを見つけて、ローカルデータベースのLocalIdより大きいリモートデータベース上のすべてのレコードにマークを付けました。しかし、ローカルデータベース上のテールレコードを必ずしも削除するとは限りませんので、すべてのメッセージを繰り返して存在を比較する必要があることがわかりました。

「良い」ソリューションがあるかどうかわかりませんが、ローカルのすべてのメッセージをリモートに読み込むと、パフォーマンスは恐ろしいものになりますか？

ああ、ほんの数個のメッセージが削除され、リモートとローカルデータセットの両方に存在する数百から100 + k個のレコードからリモートに追加される必要があります。リモートのレコードを削除済みとしてマークするかどうかを決定するロジックは、それぞれのメッセージ（同じLocalId）がローカルデータセットに存在する場合に依存します。

Answer 1

アレイはソートされているので、ループして両方のループを繰り返すことができます。以下に擬似コードを示します。

//loop over both arrays at once 
int arrayAIndex = 0; 
int arrayBIndex = 0; 
while (arrayAIndex < arrayA.length && arrayBIndex < arrayB.length) { 
    if (arrayA[arrayAIndex] == arrayB[arrayBIndex]) { 
    arrayAIndex++; 
    arrayBIndex++; 
    } else if (arrayA[arrayAIndex] > arrayB[arrayBIndex]) { 
    addToResultB(arrayBIndex); 
    arrayBIndex++; 
    } else if (arrayB[arrayBIndex] > arrayA[arrayAIndex]) { 
    addToResultA(arrayAIndex); 
    arrayAIndex++; 
    } 
} 

//clean up any elements which were not looked at during the above 
while (arrayAIndex < arrayA.length) { 
    addToResultA(arrayAIndex); 
    arrayAIndex++; 
} 
while (arrayBIndex < arrayB.length) { 
    addToResultB(arrayBIndex); 
    arrayBIndex++; 
}