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 =
Given input array A =
[1,1,2]
,
Your function should return length =
2
, and A is now [1,2]
.Analysis:
The trick is given array is already sorted, which means the duplicated elements are all together. e.g.(1,1,2,2,3,4,5,5,5,6,7,7,8,9)
From the 1st element, store current element value(from A[0]), if the current element == stored value, put all the elements one step back. e.g. A[i]=A[i+1]; then change the length of the array.
Update 201402:
Code:
class Solution { public: int removeDuplicates(int A[], int n) { if (n<2){return n;} //Forward scan /*int i=1; int pre=A[0]; int len = n; while (i<len){ if (pre==A[i]){ for(int j=i;j<len;j++){A[j]=A[j+1];} len--; }else{ pre = A[i]; i++; } }*/ // Backward Scan int i=n-2; int pre = A[n-1]; int len = n; while (i>=0){ if (pre==A[i]){ for (int j=i;j<len;j++){A[j]=A[j+1];} len--; i--; }else{ pre=A[i]; i--; } } return len; } };
what's the time complexity of this algorithm? Is it O(N^2)?
ReplyDeleteCorrect. His solution does it in O(N^2) since he moves each element back filling in the space of the duplicate element. This can be done in O(N) time with the following solution:
Deleteint removeDuplicates(vector& nums) {
if (nums.size() == 0) {
return 0;
}
int remove = nums[0];
int i = 1;
int j = 1;
while (i < nums.size()) {
if (nums[i] != remove) {
nums[j] = nums[i];
j++;
remove = nums[i];
}
i++;
}
return j;
}
This comment has been removed by the author.
ReplyDelete