java - 在 Java 中查找 int 子数组的补充

Question

让我们有 int[] A = new int[1000] 和 int[] subA = new int [300] 这样 subA\in A (subA 是 A 的子集)。如何在 Java 中以最快的方式查找数组 A\subA？给定的数组 A 和 subA 都已排序。

编辑:抱歉，忘了说数组包含不同的元素，只是它们包含另一种结构的索引，例如矩阵行。

我正在考虑这个解决方案:

// 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;
}

目前正在测试这种方法。答案准备好后我会回来。

Answer 1

尝试这样的事情:

// 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];
}