[알고리즘] Remove Duplicates from Sorted Array

문제 정보

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

[예제]
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,,,,,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

내풀이

처음엔 중복되지 않는 수의 갯수만 return해주면 되는 줄 알고 풀었는데, 자꾸 Fail이어서 자세히 보니 nums에서 k값까지 중복없이 숫자를 다시 insert해줘야했다.

예를 들어 nums가 [0,0,1,1,1,2,2,3,3,4]이면
return 5를 하고, nums는 [0,1,2,3,4,2,2,3,3,4]로 수정해줘야한다.
그래야 run했을 때 성공할 수 있다.

index를 1로 일단 주고
nums[j]와 nums[j-1]가 중복이 되지 않으면 nums[index]에 nums[j]값을 넣어주었다.

시간복잡도 : O(n)
공간복잡도 : O(1)

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

        return index;
    }
}

Runtime : 1 ms
Memory : 44.1 MB

개선하기

nums.length가 0일때는 return을 index 초기 값인 1을 해주면 안된다.
하지만 문제에 nums.length가 1부터라고 되어있어서 오류는 나지 않았다.
이건 문제의 조건마다 다르기 때문에 잘 확인해야겠다.

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

이것 이외에는 딱히 개선할 사항은 없어보인다.