a= [1,1,2]
=> a = [1,2] return new array length 2
2. Implementation
Thought 1:
Q1: detect duplicate ?
A1: keep one lastElement to compare with next element
if same, no change
if different, lastElement reset to current element
Q1: care about length
A1: how many different element, increment count (use index here so bias 1)
Q1:in-palce or how to remove duplicate element in an array ?
A1: record first duplicate happening position (index) and replace with next non-duplicate value
Thought2: check duplicate length and total length - duplicate length
Q1: duplicate length?
A1: compare with prev if equal, then duplicate length +1
// NOTE: no duplicate can happen
// NOTE: last+1 since last is index and so length should be plus 1
// NOTE :snippet
if ( nums[cur] == nums[last] ) {
cur++;
}
else {
last++;
nums[last] = nums[cur];
cur++;
}
[Array] Remove Duplicates from sorted array II
// Time:O(n), Space:O(1) public int removeDuplicates(int[] nums) { // valid the input if (nums == null || nums.length == 0) { return 0; } // NOTE: no duplicate can happen if ( nums.length < 2) { return nums.length; } int last = 0; //int lastElement = nums[0]; int cur = 1; //for (int i = 1 ; i < nums.length -1; i++ ) while (cur < nums.length ) { //if ( nums[cur] == lastElement) if ( nums[cur] == nums[last] ) { cur++; } else { last++; nums[last] = nums[cur]; cur++; } } // NOTE: last+1 since last is index and so length should be plus 1 return last+1; }
int countDup = 0; for (i=0; i < len-1;i++) { if ( nums[i] == nums[i+1]) countDup++; } return A.length - countDup;3. Similar Ones
[Array] Remove Duplicates from sorted array II
No comments:
Post a Comment