算法题--删除数组中的重复元素II

image.png

0. 链接

题目链接

1. 题目

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

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

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

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

Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

2. 思路1：双指针法

• 第一直觉是需要将合法元素通过位置交换，放到数组的前面

• 需要2个指针, 一个快，负责向右探索；一个慢，负责标记到目前位置的最后一个合法位置

• 初始化slow=0, fast=1, repeat_num=1分别表示慢指针位置、快指针位置、当前最后一个合法元素的重复次数

• 具体算法过程如下:

如果 len(nums) <= 1 则
    返回 len(nums)

while fast < 数组长度 do
    如果 nums[fast] == nums[slow] 则 
        如果 repeat_num < 2 则
            repeat_num自增1
            如果 fast - slow 不相邻，
                将fast处的元素挪到slow后面一格, 以保证重复元素相邻
                fast, slow各后移1位，以确保slow仍然表示最后一个合法元素的位置, 而fast继续探索下一个元素位置
            否则
                fast后移1位, 继续探索下一个元素位置, 
                slow后移1位，表示合法元素数又增加了一个
        否则
            slow保持不变, 这是因为当前探索到的是一个多余的重复元素，合法元素数没有变化
            fast后移1位, 继续探索下一个元素位置
    否则
        运行到此处表明遇到了新的合法元素, 则
        slow后移1位, 然后将fast跟slow元素互换, 这样slow当前指向的就是最后一个合法元素(新增的这个元素)
        而repeat_num重置为1, 表示新元素到目前为止的出现次数
        fast后移1位, 继续探索下一个元素位置

返回 slow + 1

3. 代码

# coding:utf8
from typing import List


class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return len(nums)

        slow, fast, repeat_num = 0, 1, 1
        while fast < len(nums):
            if nums[slow] == nums[fast]:
                if repeat_num < 2:
                    repeat_num += 1
                    if fast - slow > 1:
                        slow += 1
                        nums[slow], nums[fast] = nums[fast], nums[slow]
                        fast += 1
                    else:
                        slow += 1
                        fast += 1
                else:
                    fast += 1
            else:
                slow += 1
                if fast != slow:
                    nums[slow], nums[fast] = nums[fast], nums[slow]
                repeat_num = 1
                fast += 1

        return slow + 1


def my_test(solution, nums):
    print('input: {}, => output: {}'.format(nums, solution.removeDuplicates(nums)))


solution = Solution()
my_test(solution, [1, 1, 1, 2, 2, 3])
my_test(solution, [0, 0, 1, 1, 1, 1, 2, 3, 3])

输出结果

input: [1, 1, 2, 2, 3, 1], => output: 5
input: [0, 0, 1, 1, 2, 3, 3, 1, 1], => output: 7

4. 结果

image.png