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

让我们拥有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;
}

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

最佳答案

尝试这样的事情:

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