[leetcode #448] Find All Numbers Disappeared in an Array

Problem

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 <= 10⁵
・ 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.

Idea

이 문제를 가장 쉽게 푸는 건 아마 set을 이용하는 것일 것이다. set에 array의 모든 값을 넣고, 1~n까지 수 중 set에 없는 수를 list로 만들어 리턴하면 된다.

Follow up을 보면 extra space 없이 O(n)으로 풀어보라고 나온다. O(n)으로 푸는 방법은 array를 탐색하면서 i번째 값이 (i+1)이 아닐 경우 해당 값을 index로 가진 원소로 이동해 값을 (i+1)로 바꿔주는 것이다. i번째 값이 (i+1)이 될 때까지 위 과정을 반복한다. array 탐색이 끝난 뒤에 array가 가지고 있는 1~n까지의 값은 index에 맞게 설정이 된다. 이후 array를 다시 탐색하면서 array의 값이 (index+1)이 아닌 경우만 list에 더하면 된다.

Solution

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        for (int i=0; i < nums.length; i++) {
            if (nums[i] == i+1)
                continue;
            int tmp = nums[i];
            while (nums[tmp-1] != tmp) {
                int index = tmp - 1;
                tmp = nums[index];
                nums[index] = index + 1;
            }
        }

        List<Integer> res = new ArrayList<>();

        for (int i=0; i < nums.length; i++) {
            if (nums[i] != i+1)
                res.add(i+1);
        }

        return res;
    }
}

Reference

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