26. Remove Duplicates from Sorted Array （Easy）

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

solution

解法一

class Solution {    public int removeDuplicates(int[] nums) {        int newlength = 0, k = 0;        for (int i = 0; i < nums.length - 1; i++)        {            if (nums[i] < nums[i+1])   //如果两数不同            {                k = i + 1;     //记录不同两数中下一个的下标                newlength++;   //新数组长度++                if (k > newlength)    //如果k与newlength不同步，说明有重复的数                    nums[newlength] = nums[k];  将nums[k]移动到newlength处            }        }        return newlength + 1;    //此处不能用newlength++    }}

解法二

class Solution {    public int removeDuplicates(int[] nums) {        int newlength = 0;        for (int i = 0; i < nums.length; i++)        {            if (nums[newlength] != nums[i])                nums[++newlength] = nums[i];        }        return newlength+1;  //此处不能用newlength++    }}

总结

题意是给定一个排好序的数组，需要将里面不重复的数字按顺序放在数组左端，构成一个新的数组，且这些不重复数字的长度为length，超过length长度的数字不用理会。

第一种解法没第二种解法简单，故只描述第二种解法。第二种解法的思路是设置一个计数器newlength，初始值为0，然后遍历数组，如果nums[newlength] != nums[i],则将nums[++newlength]置为nums[i]，否则什么都不做；遍历完成后返回newlength+1；

Notes

1.注意++i与i++的区别；