Leetcode——[026]Remove Duplicates从排序数组中删除重复项

题目

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

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

示例：

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

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素必须是 1 和 2。

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

Given a sorted array nums, 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.

Example 1:

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 returned length.

解题方法

双指针

使用双指针，一个指向已经删除重复元素的数组最后一个元素，另一个指向需要判断是否重复的元素，比较两个数，如果两个数不一样，就进行替换，一次循环后，返回第一个指针+1，跑了12ms，代码如下。

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

一个小发现

上面代码中，for循环与if条件语句中只有一条执行语句，故可以省略大括号，但是省略之后发现运行时间增加了，跑了27ms，所以我个人建议以后Java coding时大括号还是不要省略好。注意，Method_01速度更快！

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

结语

宝剑锋从磨砺出，梅花香自苦寒来。Keep coding！

这是笔者刷leetcode的开始，代码都托管在我的Github上，有兴趣的朋友可以相互交流，请多多指教。