[leetcode 448] Find All Numbers Disappeared in an Array

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime?

You may assume the returned list does not count as extra space.

Example:

Input: [4,3,2,7,8,2,3,1] Output: [5,6]

 

문제 설명:

1부터 n까지 숫자로 구성되어 있는 배열에서 없는 숫자를 찾기

 

풀이:

- 굉장히 독특하게 접근함 : 어차피 1부터 N의 숫자로 배열이 구성되어 있는 것은 고정. 따라서 각 숫자를 인덱스로 매칭하여 체크한다.

- 예를 들어 [2, 4, 1, 1]이라고 해보자 

: [1, 2, 3, 4]에 매칭을 시켜보면 2는 사실 1의 인덱스에, 4는 3의 인덱스에 위치한다. 즉 val-1의 위치에 존재한다. 

: 그렇다면 주어진 배열 [2 4 1 1]에서 num[0]의 2를 통해 2가 있음을 표기한다. 어떻게? 2의 실제 위치는 1이므로 num[2-1]에 -1을 곱해서 2가 등장했다는 사실을 표기 한다. 

즉

idx = nums[i] -1

nums[idx] *= -1 이 되는 것이다.

 

여기서 abs를 하는 이유는 nums[idx] *= -1로 인해 nums[i]가 이미 마이너스일 수 있기 때문이다.배열을 한 번 순회하면서 체크하고

다시 한 번 순회하면서 체크되지 않은 배열이 있는지(nums[i]>0) 확인한다. 해당 위치에 해당하는 값은 i+1이므로 정답에 i+1을 추가한다.

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> answer;
        
        if(nums.size() == 0){
            return answer;
        }
        
        for(int i=0; i<nums.size(); i++){
            int idx = abs(nums[i])-1;
            nums[idx] = abs(nums[idx]) * (-1);
        }
        
        for(int i=0; i<nums.size(); i++){
            if(nums[i]>0){
                answer.push_back(i+1);
            }
        }
       
        return answer;
    }
};