LeetCode 26 号问题 删除数组中的重复项

删除数组中的重复项

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

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

示例 1:

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

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

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

示例 2:

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

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

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

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

思路

关键点

1. 排序数据
2. 不要使用额外的数组空间
3. 原地删除重复出现的元素

解决问题

• 将数组中的第一位置数 nums[0] 定义为一个校验位int cur = nums[0], 从索引为1处，对数组进行循环
  Snipaste_2019-01-15_22-55-06.png

• 将校验位cur 依次与数组中每一个索引位置的值进行比较

第一次比较 两个值相等，不做改变

Snipaste_2019-01-15_23-05-45.png

第二次比较 nums[2] != cur

这时需要替换元素位置，将cur替换为nums[2], 这时需要申明一个 int curIndex = 1; 变量，记录现在数组中存在的不重复数据的索引的位置， 初始值为 1, 同时将nums[2]的值赋值给nums[curIndex]

Snipaste_2019-01-15_23-23-23.png

上图中红色虚线框内便已经是不重复的数据

紧接着同时将index, 与 curIndex 向后移动一位, 接着循环,此时标志位cur 已经变成了2

Snipaste_2019-01-16_09-32-30.png

第三次循环比较

Snipaste_2019-01-16_09-37-39.png

标志位 cur 与 nums[3] 相等, 表明为重复元素, nums[3] 中元素已经在红色虚线框中出现过

将index 向后移动一位, curIndex 保持不变, 红色虚线框中的内容保持不变, cur 标识位保持不变

Snipaste_2019-01-16_09-41-53.png

第四次循环比较

Snipaste_2019-01-16_09-43-28.png

此时, 标志位和nums[4]不相等, 就跟步骤二一样,需要替换到 nums[curIndex] 与cur 位置处的元素

Snipaste_2019-01-16_09-49-18.png

此时同时将index 与 curIndex 向后移动一位

Snipaste_2019-01-16_09-51-12.png

第五次循环比较

Snipaste_2019-01-16_09-54-23.png

标志位 cur 与 nums[5] 相等, 表明为重复元素, nums[5] 中元素已经在红色虚线框中出现过

将index 向后移动一位, curIndex 保持不变, 红色虚线框中的内容保持不变, cur 标识位保持不变

Snipaste_2019-01-16_09-56-02.png

第六次循环比较

Snipaste_2019-01-16_09-57-52.png

不相等, 替换 curIndex 处的元素

Snipaste_2019-01-16_10-00-56.png

并向后移动 curIndex = curIndex + 1

Snipaste_2019-01-16_10-02-52.png

最后curIndex 处的位置便是题目的解

代码

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length == 0) {
            return 0;
        }
        
        int cur = nums[0];
        int index = 1;
        
        for (int i = 1; i < nums.length ; i ++) {
            if(cur != nums[i]){
                nums[index ++] = nums[i];
                cur = nums[i];
            }
        }
        return index;
    }
}