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