448. Find All Numbers Disappeared in an Array

Find All Numbers Disappeared in an Array - LeetCode

1. 집합 연산을 이용한 풀이

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        return list(set([i for i in range(1, len(nums) + 1)]) - set(nums))

하지만 집합 연산을 위한 추가 공간을 사용하고 있다.

 

2. 시간, 공간 복잡도를 O(N), O(1)로 해결하는 풀이

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        for index, num in enumerate(nums):
            t = abs(num) - 1
            nums[t] = -abs(nums[t])
        return [i + 1 for i in range(len(nums)) if nums[i] > 0]

 

배열에 등장하는 숫자는 1 ~ 배열의 길이까지이고, 특정 숫자가 등장했다는 것을 그 숫자-1 인덱스 위치에 체크(-1을 곱하기)를 한다.

해당 인덱스의 위치가 양수라면 체크가 되지 않은 위치고, 체크가 되지 않았다는 것은 그 수가 등장하지 않았다는 것을 의미한다.