力扣算法打卡刷题|??导图整理大厂面试高频数组8: 移除元素的双指针优化, 力扣27?? 算法|面试|力扣|Python|移除元素

此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解.

目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容).

关于本专栏所有题目的目录链接, 刷算法题目的顺序/注意点/技巧, 以及思维导图源文件问题请点击此链接.

想进大厂, 刷算法是必不可少的, 欢迎和博主一起打卡刷力扣算法, 博主同步更新了算法视频讲解和其他文章/导图讲解, 更易于理解, 欢迎来看!

文章目录

0.导图整理

1.双指针的思想

2.对于双指针的优化

源码

Python:

java:

题目链接: https://leetcode-cn.com/problems/remove-element/
0.导图整理

力扣算法打卡刷题|??导图整理大厂面试高频数组8: 移除元素的双指针优化, 力扣27??

文章图片

1.双指针的思想本题最重要的限制条件就是原地移除元素, 使用O(1)的额外空间. 如果没有这个条件限制, 那么本题是非常简单的, 我们只需要遍历一遍, 将所有满足的元素放到另一个数组就完成操作了. 这样就会使用到O(n)的空间复杂度.
因为限制条件的存在, 我们必须寻找其他的思想, 只能在原数组上进行操作, 这样才能满足O(1)的空间复杂度. 这样我们就不光需要找到满足的元素, 还要同时找到满足的元素需要存放的位置, 所以我们就需要使用双指针来同时确定这两个位置.
这就回到了导图中使用的思想: 右指针right指向当前将要处理的元素, 左指针left指向下一个将要赋值的位置, 这是两个指针的作用说明. 下面就是两种实际遍历中会出现的情况了.

如果右指针指向的元素不等于 val, 它一定是输出数组的一个元素, 我们就将右指针指向的元素复制到左指针位置, 然后将左右指针同时右移
如果右指针指向的元素等于 val, 它不能在输出数组里, 此时左指针不动, 右指针右移一位

在双指针进行不断遍历的过程中, 我们要从变化中寻找不变的性质: 区间[0,left) 中的元素都不等于 val。当左右指针遍历完输入数组以后, left 的值就是输出数组的长度, 这样就得到了我们最终需要的结果.
2.对于双指针的优化双指针本就是非常优秀的算法了, 但是本题还是可以对其再进行优化.
观察上面的算法可以发现, 我们都是对满足条件(会保留下来的数据)进行操作的, 但是最坏的情况下, 如果数组中没有需要移除的元素, 那两个指针就白白地从头遍历到尾了. 而且我们根据实际情况来说, 正常情况下需要移除的元素必然是远小于需要保留的元素的, 那我们直接对移除元素进行操作岂不是更有效.
所以依然使用双指针, 两个指针初始时分别位于数组的首尾, 向中间移动遍历该序列, 只是此时两指针的含义有所不同: 左指针就是直接指向需要被移除的元素val, 只要满足条件, 直接用右指针指向的元素将其替换.
这时候可能会遇到一个问题, 就是如果赋值过来的元素恰好也等于 val怎么办? 其实这并没有什么影响, 当右指针向左移动一位之后, 可以继续把右指针指向的元素的值赋值过来（左指针指向的等于 val 的元素的位置继续被覆盖）, 直到左指针指向的元素的值不等于 val 为止, 此时左指针向右移动一位.
这样两个指针在最坏的情况下合起来只遍历了数组一次。与方法一不同的是, 方法二避免了需要保留的元素的重复赋值操作.
这个方法在写代码的时候有个注意点: 就是右指针的初始值的选取(数组长度/数组长度-1), 不同的选取值决定了while的不同循环条件, 大家可以画个草图判断一下就很明了了.
源码 Python:

# 双指针方法 class Solution: def removeElement(self, nums: List[int], val: int) -> int: n = len(nums) left = 0 # 左指针从0开始,指向下一个将要赋值的位置 # 右指针从0开始,指向当前将要处理的元素 for right in range(0, n): # 右指针指向的元素不等于val,是输出数组的元素 # 将右指针指向的元素复制到左指针位置,然后将左右指针同时右移 if nums[right] != val: nums[left] = nums[right] left += 1 # 右指针指向的元素等于val,不在输出数组里,左指针不动,右指针右移一位 return left # left的值就是输出数组的长度# 双指针优化 class Solution: def removeElement(self, nums: List[int], val: int) -> int: left = 0 # 两个指针初始时分别位于数组的首尾 right = len(nums) while left < right: # 左指针等于val,将右指针元素复制到左指针的位置,右指针左移一位 if nums[left] == val: nums[left] = nums[right - 1] right-=1 else : # 左指针不等于val,左指针右移一位,右指针不动 left+=1 return left # left的值就是输出数组的长度

java:

// 双指针方法 class Solution {public int removeElement(int[] nums, int val) {int n = nums.length; int left = 0; // 左指针从0开始,指向下一个将要赋值的位置 // 右指针从0开始,指向当前将要处理的元素 for (int right = 0; right < n; right++) {// 右指针指向的元素不等于val,是输出数组的元素 // 将右指针指向的元素复制到左指针位置,然后将左右指针同时右移 if (nums[right] != val) {nums[left] = nums[right]; left++; } }// 右指针指向的元素等于val,不在输出数组里,左指针不动,右指针右移一位 return left; // left的值就是输出数组的长度 } }// 双指针优化 class Solution {public int removeElement(int[] nums, int val) {int left = 0; // 两个指针初始时分别位于数组的首尾 int right = nums.length; while (left < right) {// 左指针等于val,将右指针元素复制到左指针的位置,右指针左移一位 if (nums[left] == val) {nums[left] = nums[right - 1]; right--; } else { // 左指针不等于val,左指针右移一位,右指针不动 left++; } } return left; // left的值就是输出数组的长度 } }

感觉作者写的不错的, 别忘了点赞关注加收藏哦(一键三连)!你的支持会带给我极大的动力, 写出更多优秀文章!
我的更多精彩文章链接, 欢迎查看
各种电脑/软件/生活/音乐/动漫/电影技巧汇总(你肯定能够找到你需要的使用技巧)
力扣算法刷题根据思维导图整理笔记快速记忆算法重点内容(欢迎和博主一起打卡刷题哦)
计算机专业知识思维导图整理
最值得收藏的 Python 全部知识点思维导图整理, 附带常用代码/方法/库/数据结构/常见错误/经典思想(持续更新中)
最值得收藏的 C++ 全部知识点思维导图整理(清华大学郑莉版), 东南大学软件工程初试906科目
最值得收藏的计算机网络全部知识点思维导图整理(王道考研), 附带经典5层结构中英对照和框架简介
最值得收藏的算法分析与设计全部知识点思维导图整理(北大慕课课程)
最值得收藏的数据结构全部知识点思维导图整理(王道考研), 附带经典题型整理
最值得收藏的人工智能导论全部知识点思维导图整理(王万良慕课课程)
最值得收藏的数值分析全部知识点思维导图整理(东北大学慕课课程)
最值得收藏的数字图像处理全部知识点思维导图整理(武汉大学慕课课程)
红黑树一张导图解决红黑树全部插入和删除问题包含详细操作原理情况对比
各种常见排序算法的时间/空间复杂度是否稳定算法选取的情况改进思维导图整理
人工智能课件算法分析课件 Python课件数值分析课件机器学习课件图像处理课件
考研相关科目知识点思维导图整理
考研经验–东南大学软件学院软件工程(这些基础课和专业课的各种坑和复习技巧你应该知道)
【力扣算法打卡刷题|??导图整理大厂面试高频数组8: 移除元素的双指针优化, 力扣27??】东南大学软件工程 906 数据结构 C++ 历年真题思维导图整理
东南大学软件工程复试3门科目历年真题思维导图整理
最值得收藏的考研高等数学全部知识点思维导图整理(张宇, 汤家凤), 附做题技巧/易错点/知识点整理
最值得收藏的考研线性代数全部知识点思维导图整理(张宇, 汤家凤), 附带惯用思维/做题技巧/易错点整理
高等数学中值定理一张思维导图解决中值定理所有题型
考研思修知识点做题技巧同类比较重要会议 1800易错题思维导图整理
考研近代史知识点做题技巧同类比较重要会议 1800易错题思维导图整理
考研马原知识点做题技巧同类比较重要会议 1800易错题思维导图整理
考研数学课程笔记考研英语课程笔记考研英语单词词根词缀记忆考研政治课程笔记
Python相关技术知识点思维导图整理
Numpy常见用法全部OneNote笔记全部笔记思维导图整理
Pandas常见用法全部OneNote笔记全部笔记思维导图整理
Matplotlib常见用法全部OneNote笔记全部笔记思维导图整理
PyTorch常见用法全部OneNote笔记全部笔记思维导图整理
Scikit-Learn常见用法全部OneNote笔记全部笔记思维导图整理
Java相关技术/ssm框架全部笔记
Spring springmvc Mybatis jsp
科技相关小米手机
小米红米历代手机型号大全发布时间发布价格
常见手机品牌的各种系列划分及其特点
历代CPU和GPU的性能情况和常见后缀的含义思维导图整理