### 题目

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.

### 笨办法，整体平移数组

[1, 1，1，1, 2, 2, 2, 3]


fast找到第一个2，就把2及它之后的所有元素向前平移几个单位。就像ArrayList做的那样。之后数组变成这样，

[1, 2, 2, 2, 3]


#### 代码

public class Solution {
public int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0) { return 0; }
int slow = 0, fast = 0, end = nums.length;
while (fast < end) {
if (nums[fast] - nums[slow] > 0) {
if (fast - slow > 1) { // need to move
int gap = fast - slow - 1;
for (int j = fast; j < end; j++) {
nums[j-gap] = nums[j];
}
end -= gap;
}
slow++;
fast = slow;
}
fast++;
}
return slow+1;
}
}


### 不复制整个数组，只复制当前数字

[1, 1，1，1, 2, 2, 2, 3]


fast找到第一个2，只需要把2复制到第一个1的后面，然后fast指针接着往前走。之后数组变成这样，

[1, 2，1，1, 2, 2, 2, 3]


#### 代码

public class Solution {
public int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0) { return 0; }
int slow = 0, fast = 0;
int max = nums[slow];
while (fast < nums.length) {
if (nums[fast] > max) {
nums[++slow] = nums[fast];
max = nums[slow];
}
fast++;
}
return slow + 1;
}
}


### 把代码写得更整洁

#### 代码

Sexy! Mia…Mia…

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


Nice!