删除排序数组中的重复元素


题目

给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

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

示例 1:

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

你不需要考虑数组中超出新长度后面的元素。
示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素最多出现两次,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 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 。

你不需要考虑数组中超出新长度后面的元素。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

分析

同理, 现在拿到这类题目,我们第一时间就能想到 双指针

对于第一题, 我们用一个指针 idx 来标记元素需要插入的位置, 用另一个指针 i 来标记遍历的元素位置,依次比较两个指针对应的值,不等时移动插入指针 idx 以及 i , 相同时移动指针 i


对于第二题, 我的第一反应是, 在第一题的基础上, 增加一个 count 字段,来标记当前元素出现的此处,只有小于 3 时才会插入,否则丢弃


然后看了下大佬们的解答,发现这个 count 字段有点多余。

对于给定数组,本身是一个有序数组, 意味着,如果能够插入时,必然满足当前待插入元素 大于 前两个元素。

依照这个思路,可以把代码更加简洁化

代码

// 第一题
private static int removeDuplicates(int[] nums) {
    if (nums.length < 2) {
        return nums.length;
    }
    int idx = 0;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] != nums[idx]) {
            nums[++idx] = nums[i];
        }
    }
    return idx + 1;
}
// ---------------------------- 第二题 ------------------------------- //
private static int removeDuplicatesNoMoreThan2(int[] nums) {
    int idx = 0;
    int count = 1;
    for (int i = 1; i < nums.length; i++) {
        if (nums[idx] == nums[i]) {
            if (++count < 3) {
                nums[++idx] = nums[i];
            }
        } else {
            nums[++idx] = nums[i];
            count = 1;
        }
    }
    return idx + 1;
}
// 精简但难理解的写法
private static int ah(int[] nums) {
    int i = 0;
    for (int num : nums) {
        // i < 2 时为前两个元素, 直接插入
        // num > nums[i - 2]: 有序数组为前提,num 大于前两个数即表示 num 非重复次数大于 2 的元素
        if (i < 2 || num > nums[i - 2]) {
            nums[i++] = num;
        }
    }
    return i;
}

文章作者: peifeng
版权声明: 本博客所有文章除特別声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 peifeng !
 上一篇
长度最小的子数组 长度最小的子数组
题目 给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。 示例: 输入:s = 7, nums = [2,3,1,2,4,3]输
2020-10-20
下一篇 
合并两个有序数组 合并两个有序数组
题目 给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。 要求时间复杂度为 O(n) 说明: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n
2020-10-18
  目录