Loading...
墨滴

SuperMP

2021/04/20  阅读:38  主题:默认主题

Leetcode刷题 | 第116题:删除有序数组中的重复项 II

我们的生命不是和这种孩子的悲伤一样,迅速地消逝在夜色中吗?

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

题目:给你一个有序数组 nums,请你原地删除重复出现的元素,使每个元素最多出现两次,返回删除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组,并使用 O(1) 额外空间的条件下完成。

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

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

提示:
1 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4

分析:双指针模拟,一个指针 cur 定位当前满足删除有序数组中的重复项后的新数组 A 的最大索引位置 + 1;另一个指针 i 定位索引位置 i 的元素是否可以添加到 A 数组中。具体地,定义变量 pre2, pre1 表示新数组 A 的最后两个元素:

  • pre2 == pre1,那么只有当指针 i 处的元素不等于 pre1 时,才可以将其添加到 A 数组中(同时更新 pre2, pre1,后移指针 cur, i ),否则只后移指针 i
  • pre2 != pre1,那么不管指针 i 处的元素是否等于 pre1,都应该将其添加到 A 数组中(同时更新 pre2, pre1,后移指针 cur, i )。

Java 代码:

class Solution // 我这个垃圾,写的也是垃圾
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n <= 2return n;
        int pre2 = nums[0], pre1 = nums[1];
        int i = 2, cur = 2;
        while (i < n) {
            if (pre2 == pre1) {
                if (pre1 != nums[i]) {
                    nums[cur] = nums[i];
                    pre2 = pre1;
                    pre1 = nums[cur];
                    cur++;
                }
                i++;
            } else {
                nums[cur] = nums[i];
                pre2 = pre1;
                pre1 = nums[cur];
                i++;
                cur++;
            }
        }
        return cur;
    }
}
  • 时间复杂度为 O(N),空间复杂度为 O(1)。

再分析想一想有没有必要判断 pre2 == pre1?其实是没必要的。因为 pre2, pre1, nums[i] 的值一定是非降序的,只要 pre2 != nums[i],那么必定可以将 nums[i] 追加到 A 数组末尾,即指针 cur 处;而当 pre2 == nums[i]时,必定有 pre1 == nums[i],即不能追加到 A 数组末尾,只能继续后移指针 i

上述 Java 代码简化:

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n <= 2return n;
        int pre2 = nums[0];
        int i = 2, cur = 2;
        while (i < n) {
            if (pre2 != nums[i]) {
                nums[cur] = nums[i];
                pre2 = nums[cur - 1];
                cur++;
            }
            i++;
        }
        return cur;
    }
}

上述 Java 代码写成快慢指针版本:

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n <= 2return n;
        int slow = 2, fast = 2;
        while (fast < n) {
            if (nums[slow - 2] != nums[fast]) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++; // 不管 if 条件满不满足, fast 必定要后移一位
        }
        return slow;
    }
}

参考资料

[1]

删除有序数组中的重复项 II: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/

SuperMP

2021/04/20  阅读:38  主题:默认主题

作者介绍

SuperMP