跳至主要內容

从排序数组中删除重复项

linwu大约 1 分钟

从排序数组中删除重复项

问题描述

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

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

示例:

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

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

解题步骤

  1. 首先,我们需要确认数组是排序的。如果数组没有排序,我们需要先对其进行排序。

  2. 设置两个指针,一个快指针,一个慢指针。快指针用于遍历数组,慢指针用于标记非重复元素的最后一个位置。

  3. 当快指针遍历数组时,比较快指针和慢指针指向的元素,如果不相等,说明遇到了新的元素,将慢指针后移一位,并将快指针指向的元素值赋给慢指针。

  4. 当快指针遍历完整个数组后,慢指针的位置(加1)就是数组新的长度。

解题框架

function removeDuplicates(nums) {
    if(nums.length == 0) return 0;
    let i = 0;
    for (let j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

关注公众号

和小伙伴们一起学习

加入技术交流群

扫描二维码 备注加群