Find a supplement to a subarray of ints in Java

Question

Let we have int[] A = new int[1000] and int[] subA = new int [300] such that subA \in A (subA is a subset of A). How to find an array A \ subA in a fastest way in Java? Both given arrays A and subA are sorted.

EDIT: sorry, forgot to mention that arrays contain different elements, simply they contain indeces of another structures like matrix rows.

I'm thinking of this solution:

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

Currently testing this approach. I will be back when the answer is ready.

Answer 1

Try something like this:

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

Answer 2

If you say elements are sorted and all different, then you only need to find the index of first element of subA in A, and then just use System.arrayCopy() to copy data in most efficient way:

    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. I didn't check all the index placement and calculations, but you get the idea.