题目
Given a sorted array, 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 in place with constant memory.
For example,
Given input array 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 new length.
public class Solution { public int removeDuplicates(int[] nums) { }} Leetcode链接
算法
假设我们现在所处理的数组为nums = [1, 1, 1, 2, 2, 3]，那么我们的算法所需要进行的步骤如下：
交换nums[1]和nums[3]，将2排在第一个1的后面，此时数组变为nums =
[1, 2, 1, 1, 2, 3]交换nums[2]和nums[5]，将3排在第一个2的后面，此时数组变为nums =
[1, 2, 3, 1, 1, 2]，这就是我们所需要的数组，返回不包含重复数字的子数组[1, 2, 3]的长度3即可。
将这个过程转换为计算机可以识别的算法，就是这样：
找到第一个重复的数字(
nums[1])，我们将这个数字的位置标记为i，此时i = 1从i + 1开始，找到第一个不等于1的数字的位置，也就是第一个2的位置，我们将这个数字的位置标记为j，此时j = 3
交换i与j所对应的数字，这样第一个2就移动到了前面，重复的1就被移动到了后面。
i++，然后把j向后移动，一直移动到我们找到第一个不等于2的数字为止，再次交换i与j所对应的数字，这样3就被移动到了前面。
i++，j继续向后移动，发现j已经移动到了数组末尾，遍历结束，此时i的值就是不包含重复数字的子数组
[1, 2, 3]的长度3。
通过分析可以发现，j每次寻找的数字就是不等于nums[i - 1]，因为nums[i - 1]就是上一次出现的数字，发现了和上一次出现的数字所不同的数字就意味着我们发现了新的数字，因为整个数组是已经排序好了的，后面的数字要么是重复的，要么就是之前没有出现过的新的数字，找到这个数字之后，将它与nums[i]所对应的数字进行交换即可，因为nums[i]是一个重复的数字，不应该放在数组前面。
整个过程如下：
先找到i和j的初始位置，得到
1 1 1 2 2 3 ^ ^ | | | | i j
交换i和j所对应的数字，得到
1 2 1 1 2 3 ^ ^ | | | | i j
再次移动i和j，得到
1 2 1 1 2 3 ^ ^ | | | | i j
再次交换i和j所对应的数字，得到
1 2 3 1 2 1 ^ ^ | | | | i j
再次移动i和j，发现j超出数组边界，程序结束，返回i的值3
1 2 3 1 2 1 ^ ^ | | | | i j
Java代码如下：
public class Solution { private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } public int removeDuplicates(int[] nums) { int i = 1; while(i < nums.length && nums[i] != nums[i - 1]) i++; if(i >= nums.length) return nums.length; for(int j = i + 1; j < nums.length; i++, j++) { while(j < nums.length && nums[j] == nums[i - 1]) j++; if(j >= nums.length) break; swap(nums, i, j); } return i; }} 这种算法的时间复杂度为O(n)，空间复杂度为O(1)。