Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
What if duplicates are allowed at most twice?
For example,
Given sorted array A =
Given sorted array A =
[1,1,1,2,2,3]
,
Your function should return length =
Notes: this problem requires in-place array manipulation.5
, and A is now [1,1,2,2,3]
.Solution1: run time complexity O(n), space complexity is constant space.
public class Solution { //no need to change the given array's size, //only change the first k elements of the array which has duplicates removed. public int removeDuplicates(int[] A) { if(A == null || A.length == 0) return 0; boolean isSameTwo = false; int pre = A[0]; int count = 0; int o = 1; for(int i = 1; i < A.length; i++) { int cur = A[i]; if(cur == pre) { if(!isSameTwo) { isSameTwo = true; A[o] = cur; o++; continue; }else { count++; } }else { pre = cur; A[o] = cur; o++; isSameTwo = false; } } return A.length - count; } }Solution2: run time complexity O(n), space complexity is constant space.
public class Solution { //no need to change the given array's size, //only change the first k elements of the array which has duplicates removed. public int removeDuplicates(int[] A) { if(A.length < 2) return A.length; int pre = 1; int cur = 2; while(cur < A.length) { if(A[cur] == A[pre] && A[cur] == A[pre - 1]) { cur++; }else { pre++; A[pre] = A[cur]; cur++; } } return pre + 1; } }Solution3:run time complexity O(n), space complexity is constant space.
public class Solution { public int removeDuplicates(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int count = 1; boolean hasTwo = false; for (int i = 1; i < nums.length; i++) { if (nums[i] == nums[i - 1]) { if (!hasTwo) { nums[count] = nums[i]; count++; hasTwo = true; } else { continue; } } else { nums[count] = nums[i]; count++; hasTwo = false; } } return count; } }
No comments:
Post a Comment