массивы – How to remove elements from an array while preserving the order of the other members in O(n) using O(1) memory?

Question:

We were asked a very "simple" problem for the interview. Does anyone have any ideas how to solve?

Given a vector of ints (or an array, whatever). Remove all 1s from it, preserving the order of the other terms, in O(n) using O(1) additional memory.

You can't be tied to the JAP.

Answer:

No problem… Two pointers. One – to the current element under consideration, the second – to the place for its recording. Initially, they point to the first element. Then we just go and see what's there.

Not 1 – copy (if the pointers do not match), move both pointers.

1 – just move the pointer further…

Here is the working code :

int main(int argc, const char * argv[])
{
    int a[30];
    for(int i = 0; i < 30; ++i) a[i] = rand()%10;


    for(int i = 0; i < 30; ++i) cout << a[i] << " "; cout << endl;


    int j = 0;
    for(int i = 0; i < 30; ++i)
    {
        if (a[i] != 1) if (i != j) a[j++] = a[i];
    }

    for(int i = 0; i < j; ++i) cout << a[i] << " "; cout << endl;

}