【LeetCode_27】移除元素

刷爆LeetCode系列

• LeetCode27题：
• github地址
• 前言
• 题目描述
• 题目思路分析
• 代码实现
• 算法代码优化

LeetCode27题：

github地址

有梦想的电信狗

前言

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

题目描述

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

题目思路分析

目标分析：

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)

classSolution{public:intremoveElement(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在循环中++

// 优化版intremoveElement(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;}

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

classSolution{public:intremoveElement(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;}};

以上就是本文的所有内容了，如果觉得文章对你有帮助，欢迎 点赞⭐收藏 支持！如有疑问或建议，请在评论区留言交流，我们一起进步

分享到此结束啦
一键三连，好运连连！你的每一次互动，都是对作者最大的鼓励！征程尚未结束，让我们在广阔的世界里继续前行！ 🚀