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