[알고리즘 - LeetCode] Remove Duplicates from Sorted Array

문제

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

정렬된 수의 배열이 주어졌을 때 배열 속 중복된 수를 제거한 길이를 리턴하라.
이때, 공간복잡도는 O(1)로 유지, 즉 새로운 배열 등을 생성하지 않아야 한다.

Example 1:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5,
with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.

풀이

제출 코드 1 - 공간복잡도 O(n)

const removeDuplicates = function(nums) {
    return nums.reduce((a, c) => {
        if (a.indexOf(c) === -1) {
            a.push(c);
        }
        return a;
    }, []);
};

유니크 값이 필요한데 공간복잡도를 O(n)으로 맞추지 않아도 될 때는 reduce메소드를 자주 사용한다. 배열이나 객체 등 원하는 형태로 맞추기 쉽다.

제출 코드2 - 공간복잡도 O(1)

const removeDuplicates = function(nums) {
    for (let i = 1; i < nums.length; i++) {
        if (nums[i - 1] === nums[i]) {
            nums.splice(i, 1);
            i--;
        }
    }
    return nums.length;
};

공간복잡도를 O(1)으로 맞추라는 조건이 있어서 원배열을 수정하는 splice메소드를 사용했다.
1. 인자로 주어진 배열을 순회하며
2. 전 후의 수를 확인해서 같은 수일 시 splice로 삭제
3. 삭제 후 모든 인덱스 값 확인을 위해 순회 중인 인덱스 값 i--로 줄여주기

타 제출 코드와 실행 속도 비교

개선 사항

var removeDuplicates = function(nums) {
    if (nums.length < 1) return 0;
  
    let left = 0;
    let count = 1;
  
    for (let i = 1; i < nums.length;i++) {
        if (nums[i] !== nums[left]) {
            left++;
            nums[left] = nums[i];
            count++;
        }
    }
    return count;
};

실행 속도가 가장 빠른 코드를 가져왔는데 특별한 메소드나 방식은 없었다. 순회하는 인덱스의 전후 값을 비교하는 점은 나의 코드와 크게 다르지 않았지만 배열의 변경없이 변수만 가지고 count한 것이 한결 가벼워 보였다.
1. 배열의 길이가 1인 경우 early 리턴
2. 주어진 배열을 순회하며 전 후의 값을 비교하고
2. 같은 수가 아닌 경우 count 값을 더해서 순회를 마친 후 리턴한다.