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

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

난이도: easy

문제:

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
Return k.
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.

Constraints:

1 <= nums.length <= 3 * 104
-100 <= nums[i] <= 100
nums is sorted in non-decreasing order.

전략:

비내림차순 nums 배열의 중복 요소를 제거하는 내부함수 구현 문제.
각 요소의 상대적인 위치는 그대로 유지되어야 하고, 리턴값은 배열의 길이(유니크한 요소의 수)
우선은 Stream.distinct() 사용해서 유니크한 값만 남기면 될듯
보다 복잡도가 낮은 방식은 여전히 for loop로 해결일 것이다.
기존 remove elements의 코드를 재사용하고, 비내림차순이므로 인접 요소의 값만 비교해서 유지여부를 결정해도 괜찮을 것 같다.

https://velog.io/@1vl/LeetCodeTop-Interview-150-Array-String-Remove-Element

코드 구현:

class Solution {
    public int removeDuplicates(int[] nums) {
        int[] tempnums = Arrays.stream(nums).distinct().toArray();
        int k = tempnums.length;
        System.arraycopy(tempnums, 0, nums, 0, k);
        return k;
    }
}

실행결과:
Time: 8 ms (6.06%), Space: 46.6 MB (5.96%) - LeetHub
https://github.com/1-vL/LeetCode/tree/main/0026-remove-duplicates-from-sorted-array

개선 방안:

연습 겸 stream 사용하기는 했지만 primitive type을 참조하는 배열이라서 for-loop의 시간복잡도와 공간 복잡도가 모두 stream보다 훨씬 낮다.
역시 for 문으로도 구현해봐야...

class Solution {
    public int removeDuplicates(int[] nums) {
        int k = 0;
        for (int i=0;i<nums.length;i++) {            
            if (nums[k]!=nums[i]) {
                nums[++k]=nums[i];
            }
        }
        return k+1;
    }
}
Time: 1 ms (98.05%), Space: 43.5 MB (97.44%) - LeetHub

Discuss 탭의 타인 코드:

class Solution {
    public int removeDuplicates(int[] nums) {
        int j = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[j] = nums[i];
                j++;
            }
        }
        return j;
    }
}

회고:
역시 원시형 int 배열 같은 경우는 Stream 보다 for 문이 압도적으로 빠른 것 같다.
형태는 다르지만 for문 코드는 서로 유사한 로직인 만큼 비슷한 성능이 나왔다.