ChunNote
0%

leetCode-80:Remove Duplicates from Sorted Array II

发表于 分类于

问题描述

给定一个整数数组，数组中的元素非递减排序。要求去除数组中的重复元素，使得每个元素最多出现两次，且仍然保持非递减的顺序。要求空间复杂度为 O(1)。题目链接：**点我**

样例输入输出

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

输出：5, nums = [1,1,2,2,3,_]

解释：返回有 5 个数据，数组中前 5 个数据是剔除后的结果，数组中后面的数据的值并不重要，可以是任意的值

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

输出：7, nums = [0,0,1,1,2,3,3, _ , _ ,_]

解释：返回有 7 个数据，数组中前 7 个数据是剔除后的结果，数组中后面的数据的值并不重要，可以是任意的值

问题解法

本题如果不限制空间复杂度的话，最简单的方式就是新建一个数组来存储结果值，然后遍历原数组进行判断，将符合的值放入新数组中。但是这中做法需要 O(n) 的时间复杂度，并不满足要求。所以需要换种做法。由于数组中可能存在多于的元素，因此先从左到右将不满足条件（有多于 2 个的重复元素）的元素位置找到，然后用另一个指针遍历，将一或者两个重复元素赋值给前一个指针，每次赋值后都将前面的一个指针向后移动一位，最后前面指针的位置就是结果数组中的有效长度。代码如下

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution 
{
    public int removeDuplicates(int[] nums)
    {
        int i;
        int count = 0;
        for (i = 1; i < nums.length; i++)
        {
            if (nums[i] == nums[i - 1])
            {
                count++;
            }
            else
            {
                count = 0;
            }

            if (count == 2)
            {
                break;
            }
        }
        
        int j = i + 1;
        while (j < nums.length && nums[i] == nums[j])
        {
            j++;
        }
        
        count = 0;
        for (; j < nums.length; j++)
        {
            if (nums[j] == nums[j - 1])
            {
                count++;
            }
            else
            {
                count = 0;
            }

            if (count < 2)
            {
                nums[i] = nums[j];
                i++;
            }
        }
        
        return i;
    }
}