Leetcode-day1【80】删除有序数组中的重复项 II

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

题目

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

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

解题思路

我的思路大致如下，使用三个独立索引（指针）i,j,k，索引i用于指向结果数组末元素的后一位元素，索引j用于指向每个重复段的第一个元素，索引k用于指向每个重复段的后一个元素。所以k-j便是每个重复段中相同元素的个数，通过判断重复次数，移动索引i进行移动赋值（如果次数为1，则赋值一次；次数大于等于2，则赋值两次）。每次移动赋值完成后，j = k将k的值赋给j，使j指向下一段的第一个元素。依次类推，直到遍历到倒数第二个重复段。对于最后一个重复段，因为无法找到下一个重复段的首元索引k，所以无法得到最后一个重复段的长度，进而无法判断。所以需要单独计算一下最后一个重复段的长度，单独进行索引i的移动赋值。我的菜鸟解法如下（想了好久www）：

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0 or n ==1:
            return n
        # nums[0,i]为非重复数列
        i = 0
        j = 0
        k = j + 1
        while k <= n-1:
            if nums[j] != nums[k]:
                if k - j == 1:
                    nums[i] = nums[j]
                    i += 1
                elif k - j >= 2:
                    nums[i] = nums[j]
                    nums[i+1] = nums[j]
                    i += 2
                j = k
            k += 1
        nums[i] = nums[j] 
        if n-1-j >= 1:
            nums[i+1] = nums[j]
            return i+2
        return i+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

解题思路【学习】

双指针

原文链接：【负雪明烛】动画题解，帮助理清思路 - 删除有序数组中的重复项 II - 力扣（LeetCode）

class Solution(object):
    def removeDuplicates(self, nums):
        slow = 0
        for fast in range(len(nums)):
            if slow < 2 or nums[fast] != nums[slow - 2]:
                nums[slow] = nums[fast]
                slow += 1
        return slow

作者：fuxuemingzhu
链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/solution/fu-xue-ming-zhu-dong-hua-ti-jie-bang-zhu-yrx5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13

看了大佬的题解真是弗如远甚，我只能妙妙妙！特别是nums[fast] != nums[slow - 2]这一段，等式不成立，则说明nums[fast]所指向的元素未重复两次；等式成立，则说明nums[fast]所指向的元素已经重复两次了，巧妙地代替了计数的功能。