题目内容

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

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

e.g
给定数组 nums = [1,1,2], 

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

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

又是原地算法，吃一堑长一智。

解法一，Set去重

看到去重，脑子里首先想到的是使用Set，但又因为原地算法的限制，所以将获得新数组挨个赋值给原数组。思路和实现都不难。

var removeDuplicates = function(nums) {
    let tempArr = Array.from(new Set(nums))
    nums.length = tempArr.length
    for (let i = 0; i < tempArr.length; i++) {
        nums[i] = tempArr[i]
    }
    return nums.length
};

解法二，Splice删除重复元素

解这题的要点在于如何判断重复元素。这里，由之前第一题两数之和的巧解法想到一个思路，利用对象来存储判断该元素是否已出现。如果已经出现，那就删除当前重复的元素。

不过用这个方法也踩了个坑，坑在没想明白在什么时候处理i的自增， 以传入数组[0,0,0,1]为例，当i=1时，由于temp对象存在0，也就是for循环中if里的条件为真，此时第二个0成功被删除，但数组长度会因为元素的删除而减1，因为splice会影响原数组。

删除第二个0，i自增变为2，而数组长度也为2。由此，原数组中的第三个0不会被访问到，也不会被删除。循环也结束。

需要把自增放在else的语句块中，这样可以一直删除重复的元素，直到没有。

对于for循环使用知识的一点回顾，在这之前我一直以为for循环括号里的三个东西是一定不能少的，也因此没有想到自增语句还可以放到后面。括号里三个语句都可以没有，但是两个分号不能少。

var removeDuplicates = function(nums) {
    let temp = {}
    for (let i = 0; i < nums.length;) {
        if(temp[nums[i]]) {
            nums.splice(i, 1)
        } else {
            temp[nums[i]] = true
            i++
        }
    }
    return nums.length
};

// i + 1 会遇到两个元素相同却没有办法的问题 // 为 i 会遇到全都给删除的情况

var removeDuplicates = function(nums) {
    let temp = {}
    for (let i = nums.length; i > 0; i--) {
        temp[nums[i]] = true
        if (temp[nums[i - 1]]) {
            nums.splice(i - 1, 1)
        }
    }
    return nums.length
};

双指针法

这个解法一开始我并没有想到，是后面在题解区。简单来说，双指针法的逻辑就是，定义一前一后两个位置的下标。如果相同，其中一个下标+1继续比较，直到不同，另一个下标才+1。这样，但凡遇到不同的才加1就直到了数组所有不重复元素的长度。

对于nums[p+1] = nums[q]这句，虽然我们可以通过p++获得非重复元素的长度。但按照题目要求，我们需要把不重复的元素放到前面。

此外，再来回顾一下 ++x和x++的区别如下。由于一开始p计数为0，所以最后应该使用++p。

a = i++; //等价于a = i; i = i + 1;
b = ++i; //等价于i = i + 1; b = i;

var removeDuplicates = function(nums) {
    let p = 0, q = 1;
    while (q < nums.length) {
        if (nums[p] === nums[q]) {
            q++
        } else {
            nums[p + 1] = nums[q]
            p++;
            q++;
        }
    }
    return ++p
};

不用splice

这个解法，本质上就是上面双指针版本的简化版。

var removeDuplicates = function (nums) {
    var len = 1;
    for (var i = 1; i < nums.length; i++) {
        if (nums[i] != nums[i-1]) {
            nums[len++] = nums[i];
        }
    }
    return len
};