タイトル:

Given an array and a value, remove all instances of that value in place and return the new length.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.

考え方:

基本構想は、配列を1回遍歴し、条件を満たす数に遭遇した場合、配列の最後の値と交換することである.交換時に現在遍歴している位置が配列の有効な位置と同じである場合、演算を早期に終了する必要がある.そうでなければ遍歴を続けます.

コード:

class Solution {
public:
    int removeElement(int A[], int n, int elem) {
        for(int i = 0; i < n; i++){
            if(A[i] == elem){
                swap(A[i],A[n-1]);
                n--;
                i--;
            }
        }
        return n;
    }
};

class Solution {
public:
    int removeElement(int A[], int n, int elem) {
        int start=0;
        int end =n-1;
        
        while(start<=end)
        {
            if(A[start]==elem)
            {
                swap(A, start, end);
                end--;
            }
            else
            {
                start++;
            }
        }
        return start;
    }
    
    void swap(int A[], int i, int j)
    {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
};