LertCode- 27. Remove Element

Description
Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

分析
题目要求对一数组删除指定的元素后形成的新数组。
注意：本题要求只能在原数组的基础上修改，不准定义其他数组。因此修改完原数组后，还应当返回新数组的元素的个数。

• 思路一
  首先定义一个变量k来表示数组中与给定元素相异的个数，初始值设为0，然后从前往后逐个扫描数组，若发现与制定元素不同，则k+1，并且将该元素填入数组的第k位上，直到扫描完全部元素。扫描完成后k表示数组中与指定元素相依的元素个数，返回k即可。

• 思路二
  使用两个指针分别指向数组A的首和尾，假设i指向首，j指向尾,指定元素为elem。如果A[i]等于elem则需要替换掉该元素，我们可以从后边找一个与elem不同的元素填入该处，如果A[i]不等于elem则i加1，若A[j]等于指定元素则j减1，这样当i大于j时我们就将所有不同元素放到数组的前边了，此时i为不同元素的个数。

C语言代码

//思路一
int removeElement(int A[], int n, int elem)
{
    int i=0,j=0;
    for(i=0;i<n;i++)
    {
        if(A[i]!=elem)
        A[j++]=A[i];
    }
    return j;       
}
//思路二
int removeElement(int A[], int n, int elem)
{
    int i=0,j=n-1,k=0;
    while(i<=j)
    {
        if(A[i]==elem&&A[j]!=elem)
        {
            A[i]=A[j];
            A[j]=elem;
        }
        if(A[i]!=elem)
            i++;
        if(A[j]==elem)
            j--;
    }
    return j+1;     
//结束循环的条件时i>j,由于j每次只移动一位，因此跳出循环时j即满足j+1=i。而i只有在A[i]!=elem的时候增加，即i时数组中与elem相异的数的个数。
}
int main()
{
    int arr[]={3,2,2,3};
    int elem=2;
    removeElement(arr, 4,  3);
     return 0;
}

参考文献
[1] https://leetcode.com/problems/remove-element/#/description
[2] https://hk029.gitbooks.io/leetbook/