❤️思维导图整理大厂面试高频数组9: 删除重复元素的通解问题, 力扣26/80❤️

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

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

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

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

文章目录

• • 0.导图整理
  • 1.双指针的快慢指针法
  • 2.和 移除元素 的不同
  • 3.本题的进阶版:每个元素最多出现两次
  • 4.本题的通解扩展
  • 源码
  • • Python:
    • java:

题目链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/

0.导图整理

1.双指针的快慢指针法

上一篇 移除元素 使用的方法就是双指针的快慢指针法, 这个方法使用最重要的点就是 明确快慢指针分别代表的含义, 写代码之前一定要明确两者的具体含义, 再来写代码就比较容易了.

比如在 移除元素 之中, 我们使用的双指针: 右指针right指向当前将要处理的元素, 左指针left指向下一个将要赋值的位置. 其实在本题 删除有序数组的重复项 中, 两个指针的含义和 移除元素 之中的含义是完全相同的: 定义两个指针 fast 和 slow 分别为快指针和慢指针, 快指针表示遍历数组到达的下标位置, 慢指针表示下一个不同元素要填入的下标位置. 在表达上有点差别, 但是本质的思想是完全一致的.

2.和 移除元素 的不同

虽然在双指针的使用上, 两者的思想是一致的, 但是具体的使用过程还是有点区别的.

在 移除元素 中, 我们 需要比较的对象 是题目中的给定值, 而且是唯一固定的, 从头到尾都是没有任何变化的.

但是在本题中, 我们 需要比较的对象 不再是某个固定的元素了, 而是 快指针指向位置的前一个元素和当前元素的比较, 因为这样比较, 才能确定两个相邻的元素是否为 重复元素, 从而决定是否要保留当前元素, 这是两题最大的不同点.

还有一个小细节注意下, 因为 移除元素 中被移除的元素可能是任意一个位置的元素, 所以两个指针的下标都是 从0开始 的. 但是在本题中, 数组的第一个元素一定是被保留下来的元素, 所以我们直接从 第二个元素 开始遍历就可以了, 也就是 双指针的下标都是从1开始的.

3.本题的进阶版:每个元素最多出现两次

进阶版和原题的唯一区别就是: 并不是要把所有重复元素都删去, 而是允许 每个元素最多出现两次. 改动看似挺简单, 实则是有一定的难度的, 这也直接让本题由 简单 直接提升到 中等 的难度.

如果没有想通此题的变化, 还是比较难处理的, 很多人也有想到用一个count变量来记录每个元素出现的次数, 两次就不处理, 超过两次就进行删除等方法, 但真正实施起来还是有点绕的, 有兴趣的朋友可以自己尝试一下.

我们直接来分析改进后的不同, 也就是进行比较的两个元素变化了. 在原本的题目中, 只需要比较 快指针指向位置的前一个元素和当前元素 即可满足要求, 但是此题明显复杂的多.

首先由于我们并不知道哪些元素会重复多少次, 所以想直接通过快指针指向的元素进行区别是很困难的, 但是这时我们还可以利用慢指针来进行比较. 分析后会发现, 慢指针之前的所有元素都是我们处理好的元素, 也就是 每个元素最多出现两次, 所以如果 当前待检查元素 nums[fast] 和 nums[slow−2] 相同的话, 那么它的出现必然就超过了两次, 因为此时必然有nums[slow−2]=nums[slow−1]=nums[fast], 反正如果不相同, 也就代表 它的出现没有超过两次, 这样我们就找到了 两个需要比较的对象了, 此题也就没什么难点了.

4.本题的通解扩展

既然都已经扩展到了 每个元素最多出现两次了, 那么同样可以扩展为 每个元素最多出现k次, 这样就形成了此题的通解问题, 解决了这个问题, 只需把k替换一下, 我们就可以解决任意次数的问题了.

有了两次的经验之后, 其实这个扩展也很容易就理解了, 能够保留的前提是：与当前写入的位置前面的第 k 个元素进行比较,不相同则保留, 也就是直接比较 nums[slow - k] 和 nums[fast] 两个元素即可, 在两次的代码上稍微修改下就能实现了, 这样我们就成功的将这一类问题完美的解决了!

源码

Python:

# 删除有序数组的重复项class Solution:    def removeDuplicates(self, nums: List[int]) -> int:        if not nums:            return 0                n = len(nums)        fast = slow = 1 # 删除重复元素之后也至少剩下一个元素        while fast < n:            if nums[fast] != nums[fast - 1]: # 说明nums[fast] 和之前的元素都不同                nums[slow] = nums[fast]      # nums[fast] 的值复制到 nums[slow]                slow += 1            fast += 1                return slow # 从nums[0]到nums[slow−1]的每个元素都不相同        # 删除有序数组中的重复项II 每个元素最多出现两次class Solution:    def removeDuplicates(self, nums: List[int]) -> int:        n = len(nums)        if (n <= 2) :            return n                slow, fast = 2, 2 # 数组的前两个数必然可以被保留        while (fast < n) :            # 检查上上个应该被保留的元素nums[slow−2]是否和当前待检查元素nums[fast]相同            if nums[slow - 2] != nums[fast] :                nums[slow] = nums[fast]                slow += 1            fast += 1                return slow # 从nums[0]到nums[slow−1]的每个元素都不相同        # 通解扩展class Solution:    def removeDuplicates(self, nums: List[int]) -> int:        def solve(k): # 最多保留k位相同数字            slow = 0 # 慢指针从0开始            for fast in nums: # 快指针遍历整个数组                # 检查被保留的元素nums[slow−k]是否和当前待检查元素fast相同                if slow < k or nums[slow - k] != fast:                    nums[slow] = fast                    slow += 1            return slow # 从nums[0]到nums[slow−1]的每个元素都不相同        return solve(2)

java:

// 删除有序数组的重复项class Solution {    public int removeDuplicates(int[] nums) {        int n = nums.length;        if (n == 0) {            return 0;        }        int fast = 1, slow = 1; // 删除重复元素之后也至少剩下一个元素        while (fast < n) {            if (nums[fast] != nums[fast - 1]) { // 说明nums[fast] 和之前的元素都不同                nums[slow] = nums[fast];        // nums[fast] 的值复制到 nums[slow]                ++slow;            }            ++fast;        }        return slow; // 从nums[0]到nums[slow−1]的每个元素都不相同    }}// 删除有序数组中的重复项II 每个元素最多出现两次class Solution {    public int removeDuplicates(int[] nums) {        int n = nums.length;        if (n <= 2) {            return n;        }        int slow = 2, fast = 2; // 数组的前两个数必然可以被保留        while (fast < n) {            // 检查上上个应该被保留的元素nums[slow−2]是否和当前待检查元素nums[fast]相同            if (nums[slow - 2] != nums[fast]) {                nums[slow] = nums[fast];                ++slow;            }            ++fast;        }        return slow; // 从nums[0]到nums[slow−1]的每个元素都不相同    }}// 通解扩展class Solution {    public int removeDuplicates(int[] nums) {           return process(nums, 2);    }    int process(int[] nums, int k) { // 最多保留k位相同数字        int slow = 0; // 慢指针从0开始        for (int fast : nums) { // 快指针遍历整个数组            // 检查被保留的元素nums[slow−k]是否和当前待检查元素fast相同            if (slow < k || nums[slow - k] != fast) nums[slow++] = fast;        }        return slow; // 从nums[0]到nums[slow−1]的每个元素都不相同    }}

感觉作者写的不错的, 别忘了点赞关注加收藏哦(一键三连)!你的支持会带给我极大的动力, 写出更多优秀文章!

我的更多精彩文章链接, 欢迎查看

各种电脑/软件/生活/音乐/动漫/电影技巧汇总(你肯定能够找到你需要的使用技巧)

力扣算法刷题 根据思维导图整理笔记快速记忆算法重点内容(欢迎和博主一起打卡刷题哦)

计算机专业知识 思维导图整理

最值得收藏的 Python 全部知识点思维导图整理, 附带常用代码/方法/库/数据结构/常见错误/经典思想(持续更新中)

最值得收藏的 C++ 全部知识点思维导图整理(清华大学郑莉版), 东南大学软件工程初试906科目

最值得收藏的 计算机网络 全部知识点思维导图整理(王道考研), 附带经典5层结构中英对照和框架简介

最值得收藏的 算法分析与设计 全部知识点思维导图整理(北大慕课课程)

最值得收藏的 数据结构 全部知识点思维导图整理(王道考研), 附带经典题型整理

最值得收藏的 人工智能导论 全部知识点思维导图整理(王万良慕课课程)

最值得收藏的 数值分析 全部知识点思维导图整理(东北大学慕课课程)

最值得收藏的 数字图像处理 全部知识点思维导图整理(武汉大学慕课课程)

红黑树 一张导图解决红黑树全部插入和删除问题 包含详细操作原理 情况对比

各种常见排序算法的时间/空间复杂度 是否稳定 算法选取的情况 改进 思维导图整理

人工智能课件 算法分析课件 Python课件 数值分析课件 机器学习课件 图像处理课件

考研相关科目 知识点 思维导图整理

考研经验–东南大学软件学院软件工程(这些基础课和专业课的各种坑和复习技巧你应该知道)

东南大学 软件工程 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的性能情况和常见后缀的含义 思维导图整理