# 题目内容

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

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

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

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

你不需要考虑数组中超出新长度后面的元素。
1
2
3
4
5
6

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

# 解法一,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
};
1
2
3
4
5
6
7
8

# 解法二,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
};
1
2
3
4
5
6
7
8
9
10
11
12

// 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
2
3
4
5
6
7
8
9
10

# 双指针法

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

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

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

a = i++; //等价于a = i; i = i + 1;
b = ++i; //等价于i = i + 1; b = i;
1
2
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
};
1
2
3
4
5
6
7
8
9
10
11
12
13

# 不用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
};
1
2
3
4
5
6
7
8
9
一笔写于: 5/24/2020, 4:34:20 PM
扫码添加我的微信
个人
个人号
公众号
公众号