[LeetCode] 448. Find All Numbers Disappeared in an Array, Easy

1. 문제

• n개의 요소로 이루어진 배열 nums가 주어질 때, nums[i]는 1~n 사이에 존재하는 경우, 누락된 정수 배열을 반환하라.

 

2. 해결

function findDisappearedNumbers(nums: number[]): number[] {
    const set = new Set(nums);
    
    const max = Math.max(...set);
    
    
    for(let i = 1; i<=nums.length; i++){
        if(set.has(i)) set.delete(i);
        else set.add(i)
    }
    
    return [...set];
};

• 처음 풀이할 때 방식이다.
• Set을 이용해 중복을 제거하고, 1부터 n까지 반복하며 목록을 갱신해준다.
• 이렇게 하니까 시간이 상당히 오래걸려서 다른 사람 풀이도 한 번 봤다.

function findDisappearedNumbers(nums: number[]): number[] {
    for(let i=0;i<nums.length;i++)
        if(nums[Math.abs(nums[i])-1]>0)
            nums[Math.abs(nums[i])-1]*=-1;

    let arr = [];

    for(let i=0;i<nums.length;i++)
        if(nums[i]>0)
            arr.push(i+1);
            
    return arr;
};

• 다른 사람의 풀이 방법인데, 뭔 소린지 이해가 안갔다.
• 일단, 인덱스 마킹 기법이라는 걸 사용했는데, 원리는 해당 요소 -1 인덱스의 값을 음수 처리하여 해당 값이 있다는 걸 표현한다고 한다.

  [4,3,2,7,8,2,3,1]​

• 이 예시의 경우

index	element
0	4 3 2 -7 8 2 3 1
1	4 3 -2 -7 8 2 3 1
7	-4 -3 -2 -7 8 2 -3 -1

• 이렇게 배열 요소 값이 변경되고, 다시 반복하면서 양수인 요소의 인덱스 값 +1인 애들이 없는 정수의 집합이 된다고 한다.
• ... 어렵다.