leetcode 448. Find All Numbers Disappeared in an Array 풀이

문제: 길이가 n이고 [1, n] 사이의 숫자를 포함하는 list에서 [1, n] 사이에서 빠진 숫자를 모두 포함하는 list를 반환하라

follow up : 반환하는 list를 제외하고 추가적인 메모리를 사용하지 않으면서 O(n)의 시간 복잡도를 가지는 알고리즘을 구현해보자.

 

아이디어: input [1,1,2] output [3], input[1,1,1,2] output [3,4]와 같이 중복된 숫자를 제외하면 어떤 종류의 숫자가 있는지 파악 가능하다. set를 이용하여 차집합을 구한다.

 

코드:

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        snum = set(nums)
        ans = set(range(1,len(nums)+1))
        ans -= snum
        return ans

set를 이용하여 차집합을 구했다. 실행시간은 매우 빨랐지만 메모리 사용량이 많았다.

follow up의 추가 메모리 사용하지 않는 방법은 잘 떠오르지 않았다.

다른 사람의 풀이:

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            temp = abs(nums[i]) - 1
            if nums[temp] > 0:
                nums[temp] *= -1
        
        res = []
        for i,n in enumerate(nums):
            if n > 0:
                res.append(i+1)
        
        return res

정렬된 list의 index를 이용하여 등장한 값에 대해서는 값을 negative로 만든다.

positive한 원소에 대해서는 등장하지 않는 것으로 파악하여 정답을 반환한다.

 

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