LeetCode 27 题：移除元素

题目描述

题目链接：https://leetcode.cn/problems/remove-element/

将数组中等于 val 的元素移除。

题目思路分析

目标分析：

1. 将数组中等于 val 的元素移除
2. 原地移除，意味着时间复杂度为 O(n)，空间复杂度为 O(1)
3. 返回 nums 中与 val 值不同的元素个数

**思路：**双指针

• src：用于扫描元素，从待扫描元素的第一个开始，因此初始下标为 0
• dst：指向数组中，最后一个位置正确的元素的下标，因此初始值为 -1
• count：记录赋值的次数，赋值的次数即为数组中与 val 值不同的元素个数，初始值为 0

操作：

• nums[src] != val 时，说明：src位置的数无需被去掉，将其放在 dst 的下一个位置。
  • dst 先 ++，指向可以放入下一个无需被删除的元素的位置
  • 向 nums[dst] 赋值放入元素，之后 src++
  • 计数器 count++
• nums[src] == val 时，说明 src位置的数需要被去掉，src++略过该元素。

代码实现

• 时间复杂度：O(n)
• 空间复杂度：O(1)

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int src = 0, dst = -1;
        int count = 0;
        while(src < nums.size()) {
            if(nums[src] != val) {
                ++dst;
                nums[dst] = nums[src];
                src++;
                ++count;
            } else {
                ++src;
            }
        }
         count;
    }
};