LeetCode 27. 移除元素

LeetCode 27. 移除元素

**题目描述：**数组nums中原地移除值为val的元素，返回新数组长度

双指针：一层查找，一层覆盖

双指针：一层查找，一层覆盖

• 通过这道题大致了解erase()的大致实现

• 由这道题可知erase()函数的时间复杂度应是O(n)

同向双指针法

​ slow表示新数组下标；

​ 用fast扫描原数组，寻找用于新数组的值，找到后直接赋给slow位置即可；

​ 最终slow即为新数组元素个数。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int fast = 0;
        int slow = 0;
        for(; fast < nums.size(); ++fast) {
            if(nums[fast] != val) {
                nums[slow++] =nums[fast];//注意赋值后slow也要往前走一步
            }
        }
        return slow;
    }
};

相向双指针法

若题目描述，要确保了移动最少元素、可以改变元素的相对顺序，可以相向的双指针

• left表示新数组下标；
• left遇到用于新数组的值（非val)直接跳过，遇到val停下；
• right遇到val跳过，遇到用于新数组的值（非val)停下；
• 若left < right，则将right位置元素赋给left位置，并更新left、right；
• 两指针相遇，表示还有最后一个数需处理，故while（left <= right);
• 最终left即为新数组元素个数。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left = 0;
        int right = nums.size() - 1;
        while(left <= right) {
            while(left <= right&&nums[left] != val) {//注意left<=right确保合法
                ++left;
            }
            while(left <= right&&nums[right] == val) {
                --right;
            }
            if(left < right) {
                nums[left++] = nums[right--];//1.数组是覆盖不是swap；2.left\right要跳到下一个位置
            }
        }
        return left;
    }
};