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

LeetCode - 448. Find All Numbers Disappeared in an Array 알고리즘 문제 풀이

분류

문제 링크 : https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/

풀이

배열에 n개의 수가 들어있을 때 [1, n] 범위에 포함되어 있지 않은 원소가 무엇인지 구하는 문제이다.

n의 최댓값이 10의 5승이라 어떤 수가 나타났는지 체크하기 위한 배열을 만들어도 되지만, Follow up 부분에 다음과 같이 되어 있다.

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.

즉, (정답을 반환하기 위한 벡터를 제외하고) 추가적인 공간을 할당하지 않고 문제를 해결하라는 것이다.

nums의 길이는 n이고 원소값은 1부터 n사이의 값이므로, nums 원소를 인덱스로 활용하여 nums[nums[i]]에 접근했을 때 음수로 바꾸어준다.

이 과정이 끝나면 등장하지 않았던 수의 위치는 양수로 되어있고, 이 양수값에 접근할 수 있는 인덱스(i)에 +1을 해주면 정답을 구할 수 있다.

Discuss에서 추천과 조회수가 많은 c++ solution O(1) space 게시글에 작성된 코드와 동일하다!

소스 코드

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