I submitted an answer based on a new Array B. I scan the Array A and only put the first 1-2 of the same numbers to B. Then copy the B back to A.
It requires O(N) space. Is there any way to solve this question with O(1) space?
Yes, there is a way. Since you are returning the length of the array at the end, anything at the end of the array beyond the length you return is not considered part of your answer. Therefore, as you traverse the array, you can copy the next valid item into spots where there are 3 or more of an element in a row. This will duplicate further items, but as long as you keep moving the elements forward, the duplicates will be beyond the length you return.
In Java, here is my answer using this algorithm, using O(n) time and O(1) space:
public int removeDuplicates(int[] A) {
if(A.length < 3) return A.length;
int count = 0;
int idx=0;
for(int i=1;i<A.length;i++){
if(A[idx] == A[i])
count++;
else
count = 0;
if(count < 2)
idx++;
A[idx] = A[i];
}
return idx+1;
}
It's possible to do that. Here is my solution with comments. Only one if statement is used in loop.
/**
* Solution:
* Only difference is now we allow two duplicates. So we scan through the
* array and if we find the 3rd duplicate we just skip them.
* We know it's 3rd duplicate by comparing the itor with second last elements in
* final array (if A[itor] == A[len-2], then A[itor]==A[len-2]==A[len-1])
*/
int removeDuplicates(int A[], int n) {
if (n <= 2) return n; // no need to deal with n<=2 case.
int len = 2, itor = 2;
while (itor < n) {
if (A[itor] != A[len-2])
A[len++] = A[itor];
itor++;
}
return len;
}
Answers you've written must describe your code with more detail content. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.
This is a version in Python, with removals. Very simple. I iterated from the end of the array to make sure that item removals didn't effect future duplication checks.
def removeDuplicates(A):
if (len(A) <= 3): return len(A)
for i in range(2,len(A))[::-1]:
if A[i] == A[i-2]:
del A[i]
return len(A)
Here is my in-place solution for this question:
int removeDuplicates(int A[], int n) {
if(n <= 2) return n;
int k = 0; bool trigger = false;
for(int i = 1; i < n; i++)
if(A[i] != A[k]) {
A[++k] = A[i]; trigger = false;
}
else if (!trigger) {
A[++k] = A[i]; trigger = true;
}
if(++k < n) A[k] = '\0';
return k;
}