Problem
[1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5] -> [1, 2, 3, 4, 5]
Method 1- using 3 pointers
Method 2 - using 2 pointers
Time complexity - O(n) in both cases.
Thanks.
Remove duplicates from the sorted arrayExample
[1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5] -> [1, 2, 3, 4, 5]
Method 1- using 3 pointers
//using 3 pointers fixDuplicatesInSortedArray(Integer[] a): start = 0 end = 0 destination = 0 while(start < a.length): while(end < a.length && a[end] == a[start]): end++ end-- //copy the distinct element a[destination] = a[start] destination++ start = end + 1 end = start //null out the rest while destination < a.length: a[destination] = null return
Method 2 - using 2 pointers
//using 2 pointers fixDuplicatesInSortedArray(Integer[] a): prev = 0 curr = 1 while curr < a.length(): while curr < a.length && a[curr] == c[prev]: curr++ if curr == a.length() break prev++ a[prev] = a[curr] curr++ //null out the rest prev++ while prev < a.length: a[prev] = null return
Time complexity - O(n) in both cases.
Thanks.
0 comments:
Post a Comment