删除排序数组中的重复项

难度：简单

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

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

示例：

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12

思路分析：
实现方法一：

设置数组重复元素的个数为 count = 0
从数组第二个元素开始遍历
当遇到第一个重复的元素时 count++
当遍历到与上一个的元素不重复即不相同时此时当前元素需要向前移 n 个重复元素的位置即替换即相当于替换最近一次重复元素第一次出现的索引位置上的元素，最近一次重复元素第一次出现的位置上的元素 = 当前元素 => nums[i-count] = nums[i] && 符合循环条件则继续遍历回到第2步否则进入下一步
返回长度 n - count

实现方法二：

增加一个是重复元素且是第一次出现的位置指针 j 默认初始化为 0 ，数组遍历从 i = 1 开始
当且仅当遇到下一个不相同即不重复的元素时，更新指针位置为下一个元素(虽然是重复元素但是还是要保留第一个不能被替换) && nums[r] = nums[i]
否则指针位置不动，原数组继续遍历
数组遍历完后返回 r+1 (为什么加1？因为是索引位置，而题目要求返回的是长度)

实现方法三：
前两种方法本质上是修改而非删除，该方法是直接在数组上删除元素

代码实现：

var removeDuplicates = function(nums) {
            var count = 0;
            var n = nums.length;
            for(let i = 1;i<n;i++){
                if(nums[i] != nums[i-1]){
                    nums[i-count] = nums[i]
                }else{
                    count++;
                }
            }
            return n-count;
        };

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

← 两数之和移除元素 →

# 删除排序数组中的重复项

删除排序数组中的重复项