【刷题日记】80. 删除有序数组中的重复项 II

本次刷题日记的第 73 篇，力扣题为：80. 删除有序数组中的重复项 II，中等

一、题目描述：

80. 删除有序数组中的重复项 II ， 我们直接来刷随机题二，看看如何删除重复项

二、这道题考察了什么思想？你的思路是什么？

80. 删除有序数组中的重复项 II 给我们讲述了哪些重要的信息：

• 题目给出了一个有序的数组，数组中都是整型的数字，且数字可能会有重复多次的情况
• 题目要求我们在数组中找到重复次数大于 2 次的数字，且将这些数字按照数组顺序覆盖掉
• 最终返回结果数组的长度，另外题目要求咱们不能引入额外的空间消耗

分析

看到这里我们知道，题目给出的数组是要求我们按照顺序在原地覆盖掉出现数字大于两次的数字，并且返回出结果数组的长度

从这一点我们可以知道，如果数组长度在 2 以下，那么咱们可以直接返回数组的实际长度即可，都不用计算了

另外这里题目要求咱们空间复杂度为 O(1) ，那么我们就不要多想什么去开辟一些帮助空间来进行分处理了，方向不对，努力白费

继续看，我们知道数组是有序的，其实这个条件算是比较好的了，对于有序的数组，处理题目起来，如果是查找的话，我们很容易想到二分法，对于本次这个题，需要我们计数，且还需要再原地修改数字的话，双指针是一个比较好的方式

双指针的处理方式，在空间复杂度上是保证了一定是 O(1) ，咱们只会引入 2 个重要的变量而已，那么可以如何设计呢？

如上所述，我们可以直接从数组的第 3 个元素，即索引为 2 的元素开始遍历数组，定义一个 fast 指针，一个 slow 指针，当

num[fast] != num[slow−2],则 num[slow++]=num[fast++]num[fast] != num[slow-2], 则 num[slow++]=num[fast++] num[fast]!=num[slow−2],则num[slow++]=num[fast++]

若

num[fast] == num[slow−2] ， fast++num[fast] == num[slow-2] ， fast++ num[fast]==num[slow−2]，fast++

如上图模拟的，我们就可以知道最终，咱们只需要返回 slow 指针位置为结果数组最后一个元素的结果数组长度即可

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码

这里注意，咱们可以直接从数组的第 3 个元素开始遍历

编码如下：

func removeDuplicates(nums []int) int {
    n := len(nums)
    // 题目要求数字可以重复 2 次，那么数组长度为 2 以下的输入，咱们直接返回数组长度即可
    if n <= 2 {
        return n
    }
    slow, fast := 2, 2
    for fast < n {
        if nums[slow-2] != nums[fast] {
            nums[slow] = nums[fast]
            slow++
        }
        fast++
    }
    return slow
}

四、总结：

题目一开始就奠定了咱们空间复杂度的基调，必须是 O(1) ，这个没的说

时间复杂度的话，看了代码也非常明确，即 O(n) ， 因此咱们遍历了一遍题目中给出数组的所有元素

原题地址：80. 删除有序数组中的重复项 II

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~