LeetCode(27)Remove Element_leetcode 27

题目如下

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.

给定一个数组，数组中含有一些数，可能包含重复的元素。给定一个数element，要求把数组中等于element的元素删除之后返回新的数组的长度。本题比较好玩儿的一点儿是，结尾只要求返回新的数组的长度，并不要求返回新的数组。所以可以利用这一点来节省时间。

如果每次找到element都删除这个元素并且把剩下的元素依次向前挪动一位，显然太浪费时间。
考虑到只需要返回新的数组的长度，可以把element和数组的最后一位做个交换。这样不断地进行下去直到把数组的所有元素遍历一遍。最后element元素都在先前的交换过程中被放到了数组后面。
注意到每次做交换时，是把数组的当前最后一位和element做交换。当前最后一位可能仍然是需要删除的element，于是交换后的新元素也需要做检查。

代码如下

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

update: 2014-10-09

因为题目是只要求返回n，所以除了交换这个办法，还可以用逐步生成新数组的方法，并且这个新数组覆盖原数组。 思路和这道题remove duplicates from sorted array目非常像

class Solution {
public:
    int removeElement(int A[], int n, int elem) {
        int keep_index = 0;
        for (int index = 0; index < n; ++index) {
            if (A[index] != elem) {
                A[keep_index] = A[index];
                ++keep_index;
            }
        }
        return keep_index;
    }
};