Problem
Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
Custom Judge:
The judge will test your solution with the following code:
int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length
int k = removeDuplicates(nums); // Calls your implementation
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
If all assertions pass, then your solution will be accepted.
Example 1:
Input: nums = [1,1,1,2,2,3] Output: 5, nums = [1,1,2,2,3,_] Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).
Example 2:
Input: nums = [0,0,1,1,1,1,2,3,3] Output: 7, nums = [0,0,1,1,2,3,3,_,_] Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).
Constraints:
1 <= nums.length <= 3 * 104-104 <= nums[i] <= 104numsis sorted in non-decreasing order.
Approach
EN
KR
앞전 두 문제들과 굉장히 유사하지만 차이점이 있다면 두번까지 중복이 허용된다는 점이다. 그럼 중복을 카운트할 변수 k를 선언하면 되겠구나!
우선 0으로 k를 선언하고 배열 반복문을 돌면서 nums[i]와 nums[i+1]를 비교하고 중복이 걸릴때마다 k를 늘려준다. 배열의 원소를 제거하는건 2번째 중복 부터이니, k가 2보다 크면 해당 중복원소를 제거하고, i를 다시 줄여준다. 만약 중복 값이 아닌 새로운 원소가 나타난다면 k는 다시 0으로 초기화 해준다. (0으로 초기화 해주는 부분을 이상하게 잡아 실패가 굉장히 많았다.🥲) 마지막으로 줄어든 nums배열의 길이를 리턴한다.
code
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function(nums) {
let k=0;
for(let i=0; i<nums.length; i++) {
let val = nums[i+1];
if(val==nums[i]) {
k++;
if(k>=2) {
nums.splice(i,1);
i--;
}
}else{
k=0;
}
}
return nums.length;
};