LeetCode - 26. Remove Duplicates from Sorted Array

Problem

내림차순이 아닌 정수 배열 nums가 주어질때, 제자리에서 동일한 요소를 제거하라. 각각의 유니크한 요소들은 한 번만 등장해야 한다. 요소들의 상대적인 순서는 똑같이 유지되어야 한다. 그리고 nums의 유니크한 요소들의 수를 리턴하라.

nums의 유니크한 요소들의 수가 k라고 생각할때, 통과하기 위해서는 다음을 만족해야한다.

• 처음 k개의 요소들이 유니크한 요소가 되도록 nums배열을 바꿔야한다. 뒤에 남아있는 요소와 사이즈는 중요하지 않다.
• k를 리턴하라.

Custom Judge가 솔루션을 테스트한다.

Example 1

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 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,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).

Solution

var removeDuplicates = function(nums) {
    let k = 0;

    for(let i=1; i<nums.length; i++) {
        if(nums[k] !== nums[i]) {
            k++;
            nums[k] = nums[i]
        }
    }

    return k+1;
};

Explanation

이 문제도 제자리 알고리즘을 이용해서 해결해야한다. 제자리 알고리즘이란?
배열 빌트인 메소드를 사용하거나 새 배열을 만들어서 해결하는 것은 추가적인 저장공간을 필요로 하는 것이기 때문에 통과되지 않는다.

2개의 포인터(Two Pointers)를 사용했다.

• k는 유니크한 마지막 요소를 가리키는 포인터
• i는 동일 여부를 판별해야할 요소를 가리키는 포인터

for문을 이용해서 k포인터가 가리키는 요소가 i포인터가 가리키는 요소(k보다 뒤의 요소)랑 다르면 nums[i]는 유니크한 요소이기 때문에 k+1번째 인덱스에 해당 요소를 덮어씌운다.
마지막 요소까지 수행하면 유니크한 요소의 개수는 k+1가 된다.