LeetCode-26(Java)：Remove Duplicates from Sorted Array (从排序数组中删除重复项)

发表于 |

问题描述

Given a sorted array, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

1
2
3
4
5
6
Example:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the new length.

给定一个有序数组，你需要原地删除其中的重复内容，使每个元素只出现一次,并返回新的长度。

不要另外定义一个数组，您必须通过用 O(1) 额外内存原地修改输入的数组来做到这一点。

1
2
3
4
5
6
示例：

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

你的函数应该返回新长度 2, 并且原数组nums的前两个元素必须是1和2
不需要理会新的数组长度后面的元素

解题思路

这个问题比较简单，首先我写了一个答案，时间是15ms，排28.5%.

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int removeDuplicates(int[] nums) {
        int len = 1;
        for (int i=0;i<nums.length;i++){
            if (nums[i] != nums[len-1]){
                nums[len] = nums[i];
                len += 1;
            }
        }
        return len;
    }
}

后来我又想了一下，可以把第6和第7行代码合并，减少运算时间。时间是14ms，排53.93%.

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int removeDuplicates(int[] nums) {
        int len = 1;
        for (int i=0;i<nums.length;i++){
            if (nums[i] != nums[len-1]){
                nums[len++] = nums[i];
                // len += 1;
            }
        }
        return len;
    }
}

因为len表示长度，所以第5行代码中的nums[len-1]需要计算len-1。于是我将len表示不重复数组最后一个的位置，然后返回的时候将len+1得到新的长度。最终的代码如下所示m，时间是13ms，排92.1%.

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int removeDuplicates(int[] nums) {
        int len = 0;
        for (int i=0;i<nums.length;i++){
            if (nums[i] != nums[len]){
                nums[++len] = nums[i];
            }
        }
        return ++len;
    }
}