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

https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/

Find All Numbers Disappeared in an Array - LeetCode

Find All Numbers Disappeared in an Array - Easy

 

크기가 n인 벡터가 주어져있다.

이 벡터는 1~n 인 수들로 이루어져있는데,

이 때, 1~n중 벡터에 없는 수들을 찾아내는 문제다.

sort를 사용하면 매우 쉽다.

sort 후에 binary search를 연달아 사용해도 되고,

앞에서 부터 훑으며 1<=i<=nums.size() 인 i와 비교해줘도 된다.

그런데 이럴 경우 O(nlogn) 이 되어 시간 복잡도가 최적화가 아닌 상태로 보였다.

고민한 결과 최적화 풀이는 아래와 같다.

 

n의 범위가 100000 이하인데에 착안했다.

sort를 하지 않은 벡터를 앞에서 부터 살펴본다.

[4, 3, 2, 7, 8, 2, 3, 1] 일 경우,

1) 4 => nums[4-1] = nums[3] = 7 에 1000000 을 더해준다.

[4, 3, 2, 1000007, 8, 2, 3, 1]

 

2) 3 => nums[3-1] = nums[2] = 2 에 1000000 을 더해준다.

[4, 3, 1000002, 1000007, 8, 2, 3, 1]

 

...

 

이를 반복하는데, 1000000을 넘는 경우엔 그대로 둬도 된다.

또한 수를 고를때는 %1000000 을 해주도록 하자.

즉, nums[nums[i]%1000000 - 1] = nums[nums[i]%1000000 - 1]%p + p

 

그러면 벡터는 아래와 같이 변한다.

[1000004, 1000003, 1000002, 1000007, 8, 2, 1000003, 1000001]

이러면 8과 2는 1000000 미만인데, 이들의 index인 5,6이 한번도 안나온것을 알 수 있다.

 

전체 풀이 코드

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> ret;
        int p = 1000000;
        for (int i=0; i<nums.size(); i++) nums[nums[i]%p-1] = nums[nums[i]%p-1]%p + p;
        for (int i=0; i<nums.size(); i++) if (nums[i]<p) ret.push_back(i+1);
        return ret;
    }
};