26. Remove Duplicates from Sorte

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.</pre>
Example 2:
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.

分析

本题是要去除排序数组中出现的重复元素，返回不重复数的个数n，也就是最终数组的前n个数为不重复数。
因为数组已经排序，重复的元素一定是相邻的。假如我们设置一个计数器，遍历数组，如果元素发生变化，也就是前后两个相邻的数不一样时，我们的计数器可以加1，遍历完，最后的n就是要返回的值，但是在这个过程中数组的元素需要同时调整，以保证前n个数就是不重复的数。
我们设置一个游标nextIndex，表示下一个不重复元素在数组中的索引，用i来遍历数组，表示搜索到的位置。那么nextIndex-1就是最近找到的不重复元素，并且nums[0]~nums[nextIndex-1]都不相同。然后，我们看从nums[i]开始，是否与nums[nextIndex-1]相等，相等的话，看下一个位置的值，直到nums[i]!=nums[nextIndex-1]。此时，我们把nums[i]放到nextIndex位置，nextIndex++。如此这样，i遍历完数组，最终的nextIndex就是要返回的值。

code

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