Allow one duplicate!
s= [1,1,1,2,2,3]
You should return length = 5
new s = [1,1,2,2,3]
2. Implementation
duplicate => hash
sorted array => duplicate next to each other
keep checking and replace the second(third here since it allow a duplicate) duplicate
with the next non-duplicate character
Q1: how to know duplicate happen?
A1: keep a index to point out where duplicate happen
Q1: how to know this is third duplicate and is not allowed?
A1: keep a index to point out where duplicate happen plus one flag to indicate this is first duplicate
. So when duplicate happen and firstDuplicate flag is true, we tend to replace this duplicate (record its index) with the next non-duplicate
Q1: Can we use the method by counting how many duplicate which is beyond two duplicate happen?
A1: we can do that by keep two pointers
NOTE:
when detect first duplicate happen, we see it as a non-duplicate and increment lastIndex value //
NOTE: duplicate if ( nums.length < 2) { return nums.length; }
// Time:O(n), Space:O(1) public int removeDuplicates(int[] nums) { // validate the input // NOTE: duplicate if ( nums.length < 2) { return nums.length; } int lastIndex = 0; int iterIndex = 1; boolean firstDuplicate = fasle; while ( iterIndex < nums.length ) { if ( nums[lastIndex] == nums[iterIndex] ) { if (!firstDuplicate) { lastIndex++; firstDuplicate = true; } } else { lastIndex++; nums[lastIndex] = nums[iterIdnex]; firstDuplciate = false; } iterIndex++; } return lastIdnex+1; 0 1 2 3 4 5 l i 1,1,1,2,2,3 i1 n[0]==n[1] fl= t l++=> 1 i++ => 2 i2 n[1]==n[2] i++= > 3 i3 n[1] != n[3] l++ => 2 n[2] = n[3] i++ => 4 fl = f i4 n[2] = n[4] f1 = t l++ =>3 i++ =>5 i5 n[3] != n[5] l++ => 4 n[4] = n[5] i++ => 6 STOP }
int last = 1; int iter =2; while ( iter < nums.length ) { if (nums[iter] == nums[last] && nums[iter]== nums[last-1]) iter++ else { last++; num[last] = num[iter]; iter+= } } return last++;3. Similar Ones
Remove Duplicate from Sorted Array
No comments:
Post a Comment