[数据结构与算法] ??思维导图整理大厂面试高频数组9: 删除重复元素的通解问题力扣26/80??

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> ??思维导图整理大厂面试高频数组9: 删除重复元素的通解问题力扣26/80?? -> 正文阅读

[数据结构与算法]??思维导图整理大厂面试高频数组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]的每个元素都不相同
    }
}