此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解.
目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容).
关于本专栏所有题目的目录链接, 刷算法题目的顺序/注意点/技巧, 以及思维导图源文件问题请点击此链接.
想进大厂, 刷算法是必不可少的, 欢迎和博主一起打卡刷力扣算法, 博主同步更新了算法视频讲解 和 其他文章/导图讲解, 更易于理解, 欢迎来看!
题目链接: https://leetcode-cn.com/problems/remove-element/
本题最重要的限制条件就是 原地移除元素, 使用O(1)的额外空间. 如果没有这个条件限制, 那么本题是非常简单的, 我们只需要遍历一遍, 将所有满足的元素放到另一个数组就完成操作了. 这样就会使用到O(n)的空间复杂度.
因为限制条件的存在, 我们必须寻找其他的思想, 只能在原数组上进行操作, 这样才能满足O(1)的空间复杂度. 这样我们就不光需要找到满足的元素, 还要同时找到满足的元素需要存放的位置, 所以我们就需要使用 双指针 来同时确定这两个位置.
这就回到了导图中使用的思想: 右指针right指向当前将要处理的元素, 左指针left指向下一个将要赋值的位置, 这是两个指针的作用说明. 下面就是两种实际遍历中会出现的情况了.
如果右指针指向的元素不等于 val, 它一定是输出数组的一个元素, 我们就将右指针指向的元素复制到左指针位置, 然后将左右指针同时右移
如果右指针指向的元素等于 val, 它不能在输出数组里, 此时左指针不动, 右指针右移一位
在 双指针 进行不断遍历的过程中, 我们要从变化中寻找 不变的性质: 区间[0,left) 中的元素都不等于 val。当左右指针遍历完输入数组以后, left 的值就是输出数组的长度, 这样就得到了我们最终需要的结果.
双指针本就是非常优秀的算法了, 但是本题还是可以对其再进行优化.
观察上面的算法可以发现, 我们都是对满足条件(会保留下来的数据)进行操作的, 但是最坏的情况下, 如果数组中没有需要移除的元素, 那两个指针就白白地从头遍历到尾了. 而且我们根据实际情况来说, 正常情况下 需要移除的元素 必然是远小于 需要保留的元素的, 那我们直接对 移除元素 进行操作岂不是更有效.
所以依然使用双指针, 两个指针初始时分别位于数组的首尾, 向中间移动遍历该序列, 只是此时两指针的含义有所不同: 左指针就是直接指向需要被移除的元素val, 只要满足条件, 直接用 右指针指向的元素将其替换.
这时候可能会遇到一个问题, 就是如果赋值过来的元素恰好也等于 val怎么办? 其实这并没有什么影响, 当右指针向左移动一位之后, 可以继续把右指针指向的元素的值赋值过来（左指针指向的等于 val 的元素的位置继续被覆盖）, 直到左指针指向的元素的值不等于 val 为止, 此时左指针向右移动一位.
这样两个指针在最坏的情况下合起来只遍历了数组一次。与方法一不同的是, 方法二避免了需要保留的元素的重复赋值操作.
这个方法在写代码的时候有个注意点: 就是 右指针 的初始值的选取(数组长度/数组长度-1), 不同的选取值决定了while的不同循环条件, 大家可以画个草图判断一下就很明了了.
# 双指针方法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的值就是输出数组的长度// 双指针方法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课件 数值分析课件 机器学习课件 图像处理课件
考研相关科目 知识点 思维导图整理
考研经验–东南大学软件学院软件工程(这些基础课和专业课的各种坑和复习技巧你应该知道)
东南大学 软件工程 906 数据结构 C++ 历年真题 思维导图整理
最值得收藏的 考研高等数学 全部知识点思维导图整理(张宇, 汤家凤), 附做题技巧/易错点/知识点整理
最值得收藏的 考研线性代数 全部知识点思维导图整理(张宇, 汤家凤), 附带惯用思维/做题技巧/易错点整理
考研思修 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理
考研近代史 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理
考研马原 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理
考研数学课程笔记 考研英语课程笔记 考研英语单词词根词缀记忆 考研政治课程笔记
Python相关技术 知识点 思维导图整理
Numpy常见用法全部OneNote笔记 全部笔记思维导图整理
Pandas常见用法全部OneNote笔记 全部笔记思维导图整理
Matplotlib常见用法全部OneNote笔记 全部笔记思维导图整理
PyTorch常见用法全部OneNote笔记 全部笔记思维导图整理
Scikit-Learn常见用法全部OneNote笔记 全部笔记思维导图整理
Java相关技术/ssm框架全部笔记
科技相关 小米手机
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/118782.html
此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解. 目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容). 关...
此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解. 目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容). 关...
此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解. 目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容). 关...
摘要：此专栏文章是对力扣上算法题目各种方法的总结和归纳整理出最重要的思路和知识重点并以思维导图形式呈现当然也会加上我对导图的详解目的是为了更方便快捷的记忆和回忆算法重点不用每次都重复看题解毕竟算法不是做了一遍就能完全记住的所 ...
摘要：此专栏文章是对力扣上算法题目各种方法的总结和归纳整理出最重要的思路和知识重点并以思维导图形式呈现当然也会加上我对导图的详解目的是为了更方便快捷的记忆和回忆算法重点不用每次都重复看题解毕竟算法不是做了一遍就能完全记住的所 ...
阅读 2189·2021-09-02 15:11
阅读 1509·2019-08-30 15:43
阅读 2075·2019-08-29 13:48
阅读 2791·2019-08-26 13:55
阅读 2102·2019-08-23 15:09
阅读 2899·2019-08-23 14:40
阅读 3424·2019-08-23 14:23
阅读 2633·2019-08-23 14:20
