移除数组元素

题目描述

给定一个数组和一个值，使用就地算法将数组中所有等于这个值的元素删除，并返回新数组的长度。

元素的顺序可以更改。你不用去关心大于当前数组长度的空间里面存储的值

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.

解题思路

idx用于正在遍历的元素下标，初始为0 end用于记录更新后数组的右下标，初始为n-1 如果A[idx]!=elem,则idx加一 如果A[idx]==elem，则交换A[idx]和A[end --] 当idx == end退出循环，并判断最终end指向的元素是否等于目标值

class Solution {
          
   
public:
    int removeElement(int A[], int n, int elem) {
          
   
        //如果n=0，直接返回
        if(!n) return 0;
        int idx(0), end(n - 1);
        //从左往右遍历
        while(idx < end) {
          
   
            if(A[idx] != elem) {
          
   
                idx ++;
            } else {
          
   
                swap(A[idx], A[end]);
                end --;
            }
        }
        //退出循环的条件是idx=end，因此还要对idx指向的元素判断
        if(A[idx] == elem) end --;
        return end + 1;
    }
};