26. 删除排序数组中的重复项

描述

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

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

class Solution {
    public int removeDuplicates(int[] nums) {
        int[] ints = Arrays.stream(nums).distinct().toArray();
        for (int i = 0; i < ints.length; i++) {
            //
            nums[i] = ints[i];
        }
        return ints.length;
    }
}

最开始想到的解法，利用stream流直接进行过滤，结果为

runtime:10 ms
memory:40.1 MB

属于取巧操作。提交后看题解，解法为双指针。

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

}
结果为

runtime:1 ms
memory:40.5 MB

由于只遍历了数值一次即完成了过滤操作，因而复杂的为o(n),速度上要快上不少。

注：该解法建立在排序数组这个前提下。