[LeetCode/Top Interview 150] [Array / String] 80. Remove Duplicates from Sorted Array II

문제 링크: https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: 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.

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] <= 104
nums is sorted in non-decreasing order.

전략:

비내림차순이고, 동일한 요소가 최대 2개씩 존재하는 배열을 반환하는 것이 목표.
내부 함수 구현문제라 nums 배열을 수정할 필요도 존재함.
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.
추가 배열을 사용하지 않고 입력받은 nums 배열을 내부에서 수정해 O(1)의 추가 메모리(일정한 복잡도)를 사용해 해결해야함.

코드 구현:

class Solution {
    public int removeDuplicates(int[] nums) {
        int k = 1;
        int pre = -10001;
        for (int i=1;i<nums.length;i++) {
            if (pre == nums[i]) {
                nums[i] = 10001;
            } else {
                k++;
            }
            if (nums[i] == nums[i-1] && nums[i] != 10001) {
                pre = nums[i];
            }
        }
        Arrays.sort(nums);
        return k;
    }
}
// 문제 제약 범위 밖의 수로 중복된 수 표기 후 정렬로 뒤로 미뤄서 제거

실행결과:
Time: 2 ms (12.30%), Space: 43.9 MB (36.42%) - LeetHub
https://github.com/1-vL/LeetCode/blob/main/0080-remove-duplicates-from-sorted-array-ii/0080-remove-duplicates-from-sorted-array-ii.java

개선 방안:

정렬이나 바깥 변수와 비교하는 과정 없이 배열만 조작해서 해결할 수 있을까?
-> 2칸 단위로 비교하려면 변수로 저장하긴 해야할듯

Discuss 탭의 타인 코드:

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length <= 2) {
            return nums.length;
        }

        int index = 2;

        for (int i = 2; i < nums.length; i++) {
            if (nums[i] != nums[index - 2]) {
                nums[index] = nums[i];
                index++;
            }
        }

        return index;
    }
}

Accepted	0 ms	43.5 MB		java

회고:
정답 코드를 보니 확실히 주어진 배열의 크기에 따라 분할정복으로 생각하면 효율적인 문제였던 것 같다.