172 删除元素

原题网址：http://www.lintcode.com/zh-cn/problem/remove-element/

给定一个数组和一个值，在原地删除与值相同的数字，返回新数组的长度。

元素的顺序可以改变，并且对新的数组不会有影响。

您在真实的面试中是否遇到过这个题？ 

Yes

样例

给出一个数组 [0,4,4,0,0,2,4,4]，和值 4

返回 4 并且4个元素的新数组为[0,0,0,2]

标签 

数组 两根指针

 

思路：同删除排序数组类似，将数组分为两个部分，不包含elem的部分和余下未判断的部分，i为不包含elem部分最后一个元素的下标，j为待遍历部分第一个元素下标；

若A[j]不等于elem，A[i+1]=A[j]，等于则继续判断下一个元素，直到整个数组全部遍历完。

 

AC代码：

class Solution {
public:
    /*
     * @param A: A list of integers
     * @param elem: An integer
     * @return: The new length after remove
     */
    int removeElement(vector<int> &A, int elem) {
        // write your code here
        int size=A.size();
     if (size==0)
     {
         return 0;
     }
     int i=-1,j=0;
     while(j<size)
     {
         if (A[j]!=elem)
         {
             A[i+1]=A[j];
             i++;
             j++;
         }
         else
         {
             j++;
         }
     }
     A.resize(i+1);
     return i+1;
    }
};