Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
For example,
Given sorted array A =
[1,1,1,2,2,3]
,
Your function should return length =
5
, and A is now [1,1,2,2,3]
.A:
-----------------------------------------3 rd Pass ----------------------
错误: 没有注意到, 如果直接覆盖的话,会有重复的---------------------------------
class Solution { public: int removeDuplicates(vector<int>& nums) { if(nums.size()<2) return nums.size(); int pre = 1; for(int i =2;i<nums.size();i++) if(nums[i] != nums[pre] || nums[i] != nums[pre-1]) nums[++pre] = nums[i]; return pre+1; } };
-----------------------2 rd pass ----------------------
public class Solution { public int removeDuplicates(int[] A) { if (A.length <= 1) return A.length; int i = -1, j = 0; while (j < A.length) { if (j + 1 < A.length && A[ j] == A[j + 1]) { A[++i] = A[j++]; } // move to the last appearance of A[j] while (j + 1 < A.length && A[ j ] == A[j + 1]) { j++; } i++; A[i] = A[j]; j++; } return i + 1; } }
-----------------------------------------1 rd Pass ----------------------
多加了个flag, 来标记,是否刚刚找到个重复的。
如果是,则跳两位, 否则跳一位。
public class Solution { public int removeDuplicates(int[] A) { if(A.length <= 2){ return A.length; } //A at least has three elements int pointer=0 , runner=1; while(runner<A.length){ boolean findRepeats = false; while(runner<A.length && A[runner] == A[pointer]){ findRepeats = true; runner++; } if(runner >= A.length){ //if already found the duplicates if(findRepeats){ pointer++; A[pointer] = A[runner-1]; } break; } //now pointer value and runner value are not equal if( !findRepeats ){ pointer++; A[pointer] = A[runner]; }else{ // findRepeats, and we will allow 2 spaces A[pointer+1] = A[pointer];// coz there are repeats A[pointer+2] = A[runner]; pointer = pointer+2; } runner++; } return pointer+1; } }
No comments:
Post a Comment