080.删除有序数组中的重复项 II

作者：沉默王二
发布时间：2023-09-24T08:14:53.489+0800

---

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

给你一个有序数组 nums ，请你原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

难度

中等

示例

示例 1：

输入：nums = [1,1,1,2,2,3]

解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3]

解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。

分析

这道题很容易让我们联想到 026.删除有序数组中的重复项 ，当时我们使用的是暴力算法，先解出答案再说，因为 026.删除有序数组中的重复项 的条件限制比较严格，很难直接采用双指针的算法，今天这道题，我们打算试试双指针。

• 双指针算法使用两个指针在数据结构中遍历，如数组或链表。这种方法可以有效减少时间和空间复杂度。
• 暴力算法，也被称为朴素算法，是解决问题的一种简单直接的方法。其基本思路是先把题解出来再说，不考虑时间和空间复杂度。

首先我们来观察数组长度较小的情况下，我们应该如何解题。

如果nums.length <= 2，那么我们就不需要考虑如何处理，直接返回原数组的长度即可，因为如果存在重复项，最多也只可能出现两次。

如果nums.length == 3，我们只需要判断nums[2]和nums[0]是否相等即可，因为二者如果相等，按照有序数组这一特性，我们可以确定nums[0],nums[1],nums[2]就是相等的元素，直接除掉nums[2]返回就行了。

推算到到这一步，我们就可以将整个nums分为已检查区、检查区/排除区和未检查区来套用上面的策略。

在上述例子中，nums.length 小于 2 的情况下，我们均不用对里面的元素进行检查，或者说，已经利用规则将其自动检查了，当nums.length 等于 3 的情况下，我们也不用对nums[0],nums[1]进行检查，只需要排除第 3 个元素即可。

其实到这一步，我们的算法雏形已经浮现出来了，采取两个指针lef,rig，开始都指向2的位置，然后我们把整个nums[]分割成已检查区 和 未检查区，[0-(lef-1)]的区域为已检查区，[rig-(n-1)]为未检查区。

接下来，我们的任务就是保证已检查区内的元素个数不能超过 2。

我们向后移动rig，并且对这时的nums[rig]进行检查，如果这时候nums[rig] == nums[lef - 2]，我们就必须舍去nums[rig]，因为如果nums[rig] == nums[lef - 2]，根据数列有序的这一特性，则nums[lef - 1] == nums[lef - 2]，这样子就必然会有三个一样的数字出现，所以我们舍去nums[rig]，向后移动rig。

那如果nums[rig] != nums[lef - 2]呢？

这时候我们就要将这个新的元素纳入已检查区了，因为这表示已检查区最多也就只有一个跟nums[rig]相等的元素，所以我们就可以大胆地将其纳入已检查区。

最后的答案，自然就是已检查区的长度。

具体实现：

class Solution {

        // 如果数组长度小于等于2，则直接返回长度        if(nums.length <= 2)            return nums.length;
        // checked 表示当前检查到的位置，也是下一个要放入的位置        // checking 表示当前正在检查的位置        int checked = 2, checking = 2;
        // 遍历数组        while(checking < nums.length){            // 如果当前检查的数字和 checked 位置的前两个数字不同，            // 这意味着我们可以把这个数字放到 checked 位置            if(nums[checked - 2] != nums[checking]){                nums[checked] = nums[checking];                checked++;            }            // 无论是否复制数字，都向前移动 checking 指针            checking++;        }
        // 返回新的数组长度        return checked;    }}

OK，来看解题效率：

我们来模拟一下当前的解题过程。

题目的目标是删除有序数组中的重复项，但是每个元素最多可以出现两次。为了解决这个问题，我们使用两个指针来遍历数组。

• 指针checked：指向应当被修改的位置。
• 指针checking：遍历数组，检查每个元素是否应当被复制到checked位置。

基本思路：

当 nums[checked - 2] != nums[checking] 时，表示当前checking所指向的元素与checked前两个元素不同，因此可以被复制。

图解：

假设我们的输入数组为:

nums = [1,1,1,2,2,3,3]

初始状态：

nums:      1  1  1  2  2  3  3

pointers:  c  c

(此处 c 代表 checked 和 checking 都在此位置)

第一步：nums[checked - 2] 与 nums[checking] 相同，因此我们只移动checking：

nums:      1  1  1  2  2  3  3

pointers:  c     c

第二步：现在 nums[checked - 2] 与 nums[checking] 仍然相同，只移动checking：

nums:      1  1  1  2  2  3  3

pointers:  c        c

第三步：现在 nums[checked - 2] 与 nums[checking] 不同，复制元素：

nums:      1  1  2  2  2  3  3

pointers:  c           c

按照这样的方式继续，直到checking到达数组末尾。

最终：

nums:      1  1  2  2  3  3  3

pointers:                  c  c

返回值为checked的值：5，表示有效的元素为[1,1,2,2,3]。

总结

本题主要还是双指针算法的运用，利用双指针法可以巧妙的将整个nums分开，从而保证已检查区内的每个元素的数量不超过2。

力扣链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

给你一个有序数组 nums ，请你原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

难度

中等

示例

示例 1：

输入：nums = [1,1,1,2,2,3]

解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3]

解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。

分析

这道题很容易让我们联想到 026.删除有序数组中的重复项 ，当时我们使用的是暴力算法，先解出答案再说，因为 026.删除有序数组中的重复项 的条件限制比较严格，很难直接采用双指针的算法，今天这道题，我们打算试试双指针。

• 双指针算法使用两个指针在数据结构中遍历，如数组或链表。这种方法可以有效减少时间和空间复杂度。
• 暴力算法，也被称为朴素算法，是解决问题的一种简单直接的方法。其基本思路是先把题解出来再说，不考虑时间和空间复杂度。

首先我们来观察数组长度较小的情况下，我们应该如何解题。

如果nums.length <= 2，那么我们就不需要考虑如何处理，直接返回原数组的长度即可，因为如果存在重复项，最多也只可能出现两次。

如果nums.length == 3，我们只需要判断nums[2]和nums[0]是否相等即可，因为二者如果相等，按照有序数组这一特性，我们可以确定nums[0],nums[1],nums[2]就是相等的元素，直接除掉nums[2]返回就行了。

推算到到这一步，我们就可以将整个nums分为已检查区、检查区/排除区和未检查区来套用上面的策略。

在上述例子中，nums.length 小于 2 的情况下，我们均不用对里面的元素进行检查，或者说，已经利用规则将其自动检查了，当nums.length 等于 3 的情况下，我们也不用对nums[0],nums[1]进行检查，只需要排除第 3 个元素即可。

其实到这一步，我们的算法雏形已经浮现出来了，采取两个指针lef,rig，开始都指向2的位置，然后我们把整个nums[]分割成已检查区 和 未检查区，[0-(lef-1)]的区域为已检查区，[rig-(n-1)]为未检查区。

接下来，我们的任务就是保证已检查区内的元素个数不能超过 2。

我们向后移动rig，并且对这时的nums[rig]进行检查，如果这时候nums[rig] == nums[lef - 2]，我们就必须舍去nums[rig]，因为如果nums[rig] == nums[lef - 2]，根据数列有序的这一特性，则nums[lef - 1] == nums[lef - 2]，这样子就必然会有三个一样的数字出现，所以我们舍去nums[rig]，向后移动rig。

那如果nums[rig] != nums[lef - 2]呢？

这时候我们就要将这个新的元素纳入已检查区了，因为这表示已检查区最多也就只有一个跟nums[rig]相等的元素，所以我们就可以大胆地将其纳入已检查区。

最后的答案，自然就是已检查区的长度。

具体实现：

class Solution {

        // 如果数组长度小于等于2，则直接返回长度        if(nums.length <= 2)            return nums.length;
        // checked 表示当前检查到的位置，也是下一个要放入的位置        // checking 表示当前正在检查的位置        int checked = 2, checking = 2;
        // 遍历数组        while(checking < nums.length){            // 如果当前检查的数字和 checked 位置的前两个数字不同，            // 这意味着我们可以把这个数字放到 checked 位置            if(nums[checked - 2] != nums[checking]){                nums[checked] = nums[checking];                checked++;            }            // 无论是否复制数字，都向前移动 checking 指针            checking++;        }
        // 返回新的数组长度        return checked;    }}

OK，来看解题效率：

我们来模拟一下当前的解题过程。

题目的目标是删除有序数组中的重复项，但是每个元素最多可以出现两次。为了解决这个问题，我们使用两个指针来遍历数组。

• 指针checked：指向应当被修改的位置。
• 指针checking：遍历数组，检查每个元素是否应当被复制到checked位置。

基本思路：

当 nums[checked - 2] != nums[checking] 时，表示当前checking所指向的元素与checked前两个元素不同，因此可以被复制。

图解：

假设我们的输入数组为:

nums = [1,1,1,2,2,3,3]

初始状态：

nums:      1  1  1  2  2  3  3

pointers:  c  c

(此处 c 代表 checked 和 checking 都在此位置)

第一步：nums[checked - 2] 与 nums[checking] 相同，因此我们只移动checking：

nums:      1  1  1  2  2  3  3

pointers:  c     c

第二步：现在 nums[checked - 2] 与 nums[checking] 仍然相同，只移动checking：

nums:      1  1  1  2  2  3  3

pointers:  c        c

第三步：现在 nums[checked - 2] 与 nums[checking] 不同，复制元素：

nums:      1  1  2  2  2  3  3

pointers:  c           c

按照这样的方式继续，直到checking到达数组末尾。

最终：

nums:      1  1  2  2  3  3  3

pointers:                  c  c

返回值为checked的值：5，表示有效的元素为[1,1,2,2,3]。

总结

本题主要还是双指针算法的运用，利用双指针法可以巧妙的将整个nums分开，从而保证已检查区内的每个元素的数量不超过2。

力扣链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

给你一个有序数组 nums ，请你原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

难度

中等

示例

示例 1：

输入：nums = [1,1,1,2,2,3]

解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3]

解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。

分析

这道题很容易让我们联想到 026.删除有序数组中的重复项 ，当时我们使用的是暴力算法，先解出答案再说，因为 026.删除有序数组中的重复项 的条件限制比较严格，很难直接采用双指针的算法，今天这道题，我们打算试试双指针。

• 双指针算法使用两个指针在数据结构中遍历，如数组或链表。这种方法可以有效减少时间和空间复杂度。
• 暴力算法，也被称为朴素算法，是解决问题的一种简单直接的方法。其基本思路是先把题解出来再说，不考虑时间和空间复杂度。

首先我们来观察数组长度较小的情况下，我们应该如何解题。

如果nums.length <= 2，那么我们就不需要考虑如何处理，直接返回原数组的长度即可，因为如果存在重复项，最多也只可能出现两次。

如果nums.length == 3，我们只需要判断nums[2]和nums[0]是否相等即可，因为二者如果相等，按照有序数组这一特性，我们可以确定nums[0],nums[1],nums[2]就是相等的元素，直接除掉nums[2]返回就行了。

推算到到这一步，我们就可以将整个nums分为已检查区、检查区/排除区和未检查区来套用上面的策略。

在上述例子中，nums.length 小于 2 的情况下，我们均不用对里面的元素进行检查，或者说，已经利用规则将其自动检查了，当nums.length 等于 3 的情况下，我们也不用对nums[0],nums[1]进行检查，只需要排除第 3 个元素即可。

其实到这一步，我们的算法雏形已经浮现出来了，采取两个指针lef,rig，开始都指向2的位置，然后我们把整个nums[]分割成已检查区 和 未检查区，[0-(lef-1)]的区域为已检查区，[rig-(n-1)]为未检查区。

接下来，我们的任务就是保证已检查区内的元素个数不能超过 2。

我们向后移动rig，并且对这时的nums[rig]进行检查，如果这时候nums[rig] == nums[lef - 2]，我们就必须舍去nums[rig]，因为如果nums[rig] == nums[lef - 2]，根据数列有序的这一特性，则nums[lef - 1] == nums[lef - 2]，这样子就必然会有三个一样的数字出现，所以我们舍去nums[rig]，向后移动rig。

那如果nums[rig] != nums[lef - 2]呢？

这时候我们就要将这个新的元素纳入已检查区了，因为这表示已检查区最多也就只有一个跟nums[rig]相等的元素，所以我们就可以大胆地将其纳入已检查区。

最后的答案，自然就是已检查区的长度。

具体实现：

class Solution {

        // 如果数组长度小于等于2，则直接返回长度        if(nums.length <= 2)            return nums.length;
        // checked 表示当前检查到的位置，也是下一个要放入的位置        // checking 表示当前正在检查的位置        int checked = 2, checking = 2;
        // 遍历数组        while(checking < nums.length){            // 如果当前检查的数字和 checked 位置的前两个数字不同，            // 这意味着我们可以把这个数字放到 checked 位置            if(nums[checked - 2] != nums[checking]){                nums[checked] = nums[checking];                checked++;            }            // 无论是否复制数字，都向前移动 checking 指针            checking++;        }
        // 返回新的数组长度        return checked;    }}

OK，来看解题效率：

我们来模拟一下当前的解题过程。

题目的目标是删除有序数组中的重复项，但是每个元素最多可以出现两次。为了解决这个问题，我们使用两个指针来遍历数组。

• 指针checked：指向应当被修改的位置。
• 指针checking：遍历数组，检查每个元素是否应当被复制到checked位置。

基本思路：

当 nums[checked - 2] != nums[checking] 时，表示当前checking所指向的元素与checked前两个元素不同，因此可以被复制。

图解：

假设我们的输入数组为:

nums = [1,1,1,2,2,3,3]

初始状态：

nums:      1  1  1  2  2  3  3

pointers:  c  c

(此处 c 代表 checked 和 checking 都在此位置)

第一步：nums[checked - 2] 与 nums[checking] 相同，因此我们只移动checking：

nums:      1  1  1  2  2  3  3

pointers:  c     c

第二步：现在 nums[checked - 2] 与 nums[checking] 仍然相同，只移动checking：

nums:      1  1  1  2  2  3  3

pointers:  c        c

第三步：现在 nums[checked - 2] 与 nums[checking] 不同，复制元素：

nums:      1  1  2  2  2  3  3

pointers:  c           c

按照这样的方式继续，直到checking到达数组末尾。

最终：

nums:      1  1  2  2  3  3  3

pointers:                  c  c

返回值为checked的值：5，表示有效的元素为[1,1,2,2,3]。

总结

本题主要还是双指针算法的运用，利用双指针法可以巧妙的将整个nums分开，从而保证已检查区内的每个元素的数量不超过2。

力扣链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412