问题描述

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

给你一个有序数组，将数组中第一次出现的元素从头往后排列，并返回其长度。

举个例子：

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5,   
with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.

解法1

Thanks [Y总]

典型的双指针问题。

核心在于找到所有第一次出现的所有元素，那么如何找？

使用一个指针i从头到尾遍历整个数组，如果当前元素与前一个元素不相等，

那么当前元素就是第一次出现的元素，因为数组是升序排列的。

然后，再用一个指针j代表截止至唯一元素的边界。

最后，非常巧妙，j就是要求的长度。

来看下整体流程：

注意，第一个元素特判一下。

来看下实现：

class Solution {
    public int removeDuplicates(int[] nums) {

        int n = nums.length;
        int j = 0;
        for (int i = 0; i < n; i++){
            if (i == 0 || nums[i] != nums[i - 1]){
                nums[j++] = nums[i];
            }
        }
        return j; 
    }
}

Enjoy it !