[LeetCode] 80. Remove Duplicates from Sorted Array II - 문제풀이

Description

주어진 오름차순으로 정렬된 배열에서 최대 2개 까지만 중복을 허용 하도록 재구성하여 반환하는 문제입니다. in-place로 추가 공간을 사용하지 않고 해결해야 합니다.

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 * 10^4
• -10^4 <= nums[i] <= 10^4
• nums is sorted in non-decreasing order.

Solution 1. Two Point

public int removeDuplicates(int[] nums) {
    int len = nums.length;
    int idx = 0;
    for(int num : nums){
        if(idx < 2 || nums[idx-2] < num ){
            nums[idx++] = num;
        }
    }
    return idx;
}

값을 채워넣을 포인터(idx)를 정의하고 먼저 2개의 값을 넣은 후 이후 값은 2개 이전의 값(idx-2)보다 클경우만 추가해줍니다. 정렬된 정수의 배열이기 때문에 2개이전의 값보다 크다면 값이 다르다는 것을 보장해줍니다.

Reference

Remove Duplicates from Sorted Array II - LeetCode