LeetCode27题：

github地址

有梦想的电信狗

前言

本文用C++实现LeetCode 第27题

题目描述

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

在这里插入图片描述

题目思路分析

目标分析：

将数组中等于val的元素移除
原地移除，意味着时间复杂度为O(n)，空间复杂度为O(1)
返回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;}}return count;}
};

算法代码优化

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

通过观察我们发现：

dst和count自增的次数一样，且初值分别为0和-1，因此count == dst + 1
且while循环内，if和else逻辑中，都执行了src++，因此if和else中的src++可以省略，直接将src在循环中++

 // 优化版
int removeElement(vector<int>& nums, int val) {int src = 0, dst = -1;while(src < nums.size()){if(nums[src] != val){++dst;nums[dst] = nums[src];}++src;}return dst + 1;
}

利用前置和后置++的特性最终优化，但不推荐这么写，因为算法的可读性下降了

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