LeetCode (80) - Remove Duplicates from Sorted Array II

하단 Title 클릭 시 해당 문제 페이지로 이동합니다.

- Remove Duplicates from Sorted Array II

• Acceptance: 50.2%
• Difficulty: Medium

문제 설명

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.

• 1 <= nums.length <= 3 * 10^4
• -104 <= nums[i] <= 104
• nums is sorted in non-decreasing order.

예시 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).

예시 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).

문제 풀이

• before = Integer.MIN_VALUE로 초기화하여 범위 밖으로 설정한다.
• moreThanTwo를 이용해 현재값이 두번 연속 나왔다면 true.
• 후에 정렬을 통해 더미값을 뒤로 보내기 위해 2개를 초과해 중복된 값은 Integer.MAX_VALUE로 설정

1. for문을 통해 일단 result값을 ++

2. before값과 nums[i]를 비교하여 다르다면 다음 검사를 위해 before = nums[i]로 변경. moreThanTwo = false

3. before 와 nums[i]가 같을때, moreThanTwo=true라면 두번을 초과한것이기에 result--, nums[i]를 Integer.MAX_VALUE로 변경한다. 또한 before == nums[i]는 두번 연속 나왔다는 말이기때문에 마지막에 moreThanTwo 값을 true로 변경.

4. 정렬을 통해 위치를 수정.

코드

import java.util.Arrays;

class Solution {
    public int removeDuplicates(int[] nums) {
        boolean moreThanTwo = false;
        int before = Integer.MIN_VALUE, result = 0;

        for (int i = 0, length = nums.length; i < length; i++) {
            result++;
            if (before == nums[i]) {
                if (moreThanTwo) {
                    result--;
                    nums[i] = Integer.MAX_VALUE;
                }
                moreThanTwo = true;
            }else {
                before = nums[i];
                moreThanTwo = false;
            }
        }

        Arrays.sort(nums);

        return result;
    }
}