leetcode 刷题记：26. 删除有序数组中的重复项

这道题如果在实际工作中其实不容易遇到，因为想把一个数组去重，一个Set就足以。然而这道题有猫腻：原地修改。

问题描述

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

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

// @algorithm @lc id=26 lang=javascript 
// @title remove-duplicates-from-sorted-array
// @test([1,1,2])=2
// @test([0,0,1,1,1,2,2,3,3,4])=5

解题思路

原本我就是使用Set来做这道题的，最后发现一直给我报错。问题就出在原地上。

function unique(array) {
    return Array.from(new Set(array));
}

这里要把数组原地替换，把第一次出现的元素移到重复的元素位置上，实现原地修改。

因为整个数组是有顺序的，就可以用比大小的方式来判断相邻两个元素是否是相同。这里使用快慢指针的方式解决这个问题，i是插入操作指针，j是遍历指针。只要判断j指针的元素大于或者不等于i，就更新i+1位置的元素为j指针的元素。

代码：

/**
 * @param {number[]} nums
 * @return {number}
 */
const removeDuplicates = function(nums) {
    if (nums.length === 0) return 0;
    let i = 0; let j = 1;
    while (j <= nums.length - 1) {
        if (nums[i] === nums[j]) j++;
        if (nums[i] < nums[j]) {
            nums[i + 1] = nums[j];
            i++;
        }
    }
    return i + 1;
};

题外话

上面提到的Set去重数组，如果数组元素是个Object，记得深度拷贝。否则会出现去重后的数组会影响原来的数组。

我一般的深度拷贝是用下面这种，主要是我也没写代码实现过这东西。

JSON.parse(JSON.stringify(array))