26. 删除排序数组中的重复项 - 力扣（LeetCode）

发表于 更新于 分类于 阅读次数： Disqus：

题目描述

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。 示例1:

1
2
3
给定数组 nums = [1,1,2], 
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 
你不需要考虑数组中超出新长度后面的元素。

示例2：

1
2
3
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。

题解

首先数组是有序的，若相邻两元素相等，则存在重复元素（计数器cnt加1）那么移除重复元素后，原位置i的元素现在应在i-cnt处，即nums[i - cnt] = nums[i]。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int len = nums.size(); //获取数组长度
        int cnt = 0;//统计重复元素
        for(int i = 1; i < len; ++i){
            if(nums[i] == nums[i - 1]){//元素重复
                ++cnt;
            }
            else{
                nums[i - cnt] = nums[i];//元素前移
            }
        }
        return len - cnt;
    }
};

运行结果

官方题解

采用双指针，一个快指针j，一个慢指针i，如果相邻元素相等，j++；如果不等，则i++，并把不等的元素复制到i处即 nums[i] = nums[j]，重复相同过程，直到j指向数组末尾。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int len = nums.size(); //获取数组长度
        int i = 0, j = 1;
        if(len == 0){//数组长度为0直接返回0
            return 0;
        }
        for(j = 1; j < len; ++j){
            if(nums[j] != nums[i]){//元素不等时，移动指针i，并进行复制操作。
                ++i;
                nums[i] = nums[j];
            }
        }
        return i + 1;
    }
};

执行结果