题目描述
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 A =[1,1,2],
Your function should return length =2, and A is now[1,2].
- 思路
给定一个排序后的数组，求去重后的数组长度以及不使用额外空间在数组上去重。
法一：标记法。将第一个数减一作为标记值，从第二个数开始遍历，每次遍历的数与之前的数相等则设置为标记值。最后将没有标记值的数直接按顺序移动到相应的位置。一共需要两次数组的遍历，若第一个数是最小值时，可以循环找到第一个不存在的数当做标记位按上述方式求解。
法二：改进的算法。一次遍历，设置下一个要覆盖数的下标为cnt，还可以表示总共不重复个数。每当与前面的数不想等时将当前覆盖到此位置，cnt自增。
//标记法（不使用额外空间）
public class Solution {
public int removeDuplicates(int[] A) {
if(A == null || A.length == 0)
return 0;
if(A.length == 1)
return 1;
int ans = A.length;
int k = A[0] - 1;
int pre = A[0];
for(int i=1; i<A.length; i++){
if(A[i] == pre){
pre = A[i];
A[i] = k;
ans --;
}else{
pre = A[i];
}
}
int j = 1;
for(int i=1; i<A.length; i++){
if(A[i] != k){
A[j] = A[i];
j ++;
}
}
return ans;
}
}
//方法二
public class Solution {
public int removeDuplicates(int[] A) {
if(A == null || A.length == 0)
return 0;
if(A.length == 1)
return 1;
int cnt = 1;
for(int i=1; i<A.length; i++){
if(A[i] != A[i-1]){
A[cnt ++] = A[i];
}
}
return cnt;
}
}
