Remove Duplicates from Sorted Array
For example:
Given input array A = [1,1,2];
Your function should return length = 2, and A is now [1,2].</ br>
Version 1:
public int removeDuplicates(int[] A) {
if (A.length == 0 || A == null) {
return 0;
}
int size = 0;
for (int i = 0; i < A.length; i++) {
if (A[i] != A[size]) {
size++;
A[size] = A[i];
}
}
return size + 1;
}
Version 2:
public int removeDuplicates(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int element = A[0];
int index = 0;
for (int i = 0; i < A.length; i++) {
if (element != A[i]) {
index++;
A[index] = A[i];
element = A[i];
}
}
return index + 1;
}
What if duplicates are allowed at most twice?For example:
Given sorted array A =
[1,1,1,2,2,3];Your function should return length =
5, and A is now [1,1,2,2,3].
Version 1:
public int removeDuplicates(int[] A) {
if (A.length <= 2) {
return A.length;
}
int prev = 1;
int curr = 2;
while (curr < A.length) {
if (A[curr] == A[prev] && A[curr] == A[prev - 1]) {
curr++;
} else {
prev++;
A[prev] = A[curr];
curr++;
}
}
return prev + 1;
}
Version 2:
public int removeDuplicates(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int size = 0;
for (int i = 1; i < A.length; i++) {
if (A[i] == A[size] && size > 0 && A[size - 1] == A[size]) {
continue;
}
A[++size] = A[i];
}
return size + 1;
}
No comments:
Post a Comment