[Leetcode] Find All Numbers Disappeared in an Array ★★★★★

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

 

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]

Output: [5,6]

Example 2:

 

Input: nums = [1,1]

Output: [2]

 

Constraints:

• n == nums.length
• 1 <= n <= 105
• 1 <= nums[i] <= n

Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

 

- Hash기반의 unordered_set도 생각했으나 추가 메모리 공간의 정의 없이 O(n) 안에 해결하는 Solution이 아니므로 패스했다. 

- 도저히 어떻게 해야할지 몰라서 검색을 했는데, 추가 배열을 정의하지 않기 위해 nums의 각 원소값에 해당하는 index의 절대값-1 (최소값인 1이면 index 0에 매핑하기 위해서) 을 음수로 표기하는 방법으로 해결한 풀이가 있었다. 

- 입력은 1 이상만 들어오므로 가능한 방법인 것 같다. 매우 생소한 방법이었으므로 여러번 복습해두자. 

 

[ 참고 코드 ]

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums)
	{
		vector<int> resultVec;

		for (auto i = 0; i < nums.size(); i++)
		{
			int m = abs(nums[i]) - 1;
			nums[m] = -abs(nums[m]);
		}

		for (auto i = 0; i < nums.size(); i++)
		{
			if (nums[i] > 0)
				resultVec.push_back(i + 1);
		}

		return resultVec;
    }
};