5

(は のサブセット)などを考えint[] A = new int[1000]てみましょう。Javaで最速の方法で配列を見つける方法は? 指定された配列と の両方がソートされます。int[] subA = new int [300]subA \in AsubAAA \ subAAsubA

編集:申し訳ありませんが、配列にはさまざまな要素が含まれていることを忘れていました。単に行列の行などの別の構造のインデックスが含まれているだけです。

私はこの解決策を考えています：

// supp is short for supplement
int[] supp = new int[A.length - subA.length];
int j = A[0], c = 0;
for (int i = 0; i < subA.lengh; i++) {
    // elegantly can be: while (j < subA[i]) supp[c++] = j++;
    while (j < subA[i]) {
        supp[c] = j;
        c++; j++;
    }
    j = subA[i] + 1;
}

現在、このアプローチをテストしています。答えの準備ができたら戻ってきます。

4

4 に答える 4

4

次のようなことを試してください：

// A index
int ai = 0;
// subA index
int sai = 0;
// result array
int[] result = new int[A.length - subA.length];
// index in result array
int resi = 0;

while ai < A.length && sai < subA.length;
    // same elements - ignore
    if (A[ai] == subA[sai]) {
        ai++;
        sai++;
    // found an element in A that does not exist in subA
    } else {
        // Store element
        result[resi] = A[ai];
        resi++;
        ai++;
    }
}

// Store elements that are left in A
for (;ai < A.length; ai++, resi++) {
    result[resi] = A[ai];
}
于 2012-11-02T11:05:31.620 に答える
1

要素がソートされ、すべてが異なると言う場合は、A の subA の最初の要素のインデックスを見つけるだけでSystem.arrayCopy()よく、最も効率的な方法でデータをコピーするために使用するだけです。

    int index = Arrays.binarySearch(A, subA[0]);

    int[] diff = new int[A.length - subA.length];

    System.arraycopy(A, 0, diff, 0, index);
    System.arraycopy(A, index+subA.length, diff, index, A.length-index-subA.length);

PS。すべてのインデックスの配置と計算を確認したわけではありませんが、おわかりいただけたでしょうか。

于 2012-11-02T12:38:37.673 に答える