448. Find All Numbers Disappeared in an Array - python3

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.

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.

My Answer 1: Time Limit Exceeded (29 / 33 test cases passed.)

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        nums.sort()
        
        ans = []
        for i in range(1, len(nums)+1):
            if i not in nums:
                ans.append(i)
        return ans

sort 해서 1 ~ n 의 숫자가 없으면 ans 에 append

왜 타임리밋인가 생각해보니... O(n^2) 이라서 그런듯...
(sort 는 O(n log n))

그리고 중복되는 숫자가 많을 경우 비효율각..

My Answer 2: Accepted (Runtime: 372 ms - 44.14% / Memory Usage: 24.2 MB - 39.02%)

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        arr = set(nums)
        
        ans = []
        for i in range(1, len(nums)+1):
            if i not in arr:
                ans.append(i)
        return ans

중복을 없애주는 set 를 이용해서 unique 한 숫자들 중에 없는 숫자 찾기

근데 이건 Follow up 을 만족하지는 않음 => extra space 사용

---

Solution 1: Accepted (Runtime: 416 ms - 17.44% / Memory Usage: 22 MB - 74.59%)

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            nums[abs(nums[i]) - 1] = - abs(nums[abs(nums[i]) - 1])
            # 이걸 풀어서 쓸 경우
            # index = abs(nums[i]) - 1
            # nums[index] = - abs(nums[index])
        
        ans = []
        for i in range(len(nums)):
            if nums[i] > 0:
                ans.append(i+1)

        return ans

인덱스를 이용하면 extra space 없이 주어진 nums 리스트로만 처리 가능

존재하는 걸 확인한 nums[i] 에 대응되는 인덱스 값을 음수로 바꿔주기 => -nums[abs(nums[i]) - 1]
(nums[i] 는 1 ~ n 의 값이므로 모두 양수인 점을 이용)

최종적으로 등장하지 않은 숫자들의 인덱스 값만 양수가 됨 => ans 에 추가해서 return

O(n) runtime 과 no extra space 모두 만족
(ans 는 extra space 가 아니라고 주어짐)

Solution 2: Accepted (Runtime: 368 ms - 47.71% / Memory Usage: 22 MB - 65.94%)

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            nums[(nums[i]%len(nums))-1] += len(nums)
        
        ans = []
        for i in range(len(nums)):
            if nums[i] <= len(nums):
                ans.append(i+1)

        return ans

비슷한 방식인데 abs 사용하는 음수 대신

존재하는 값들의 인덱스에 전체 길이 len(nums) 을 더해주고 len(nums) 보다 작은 숫자들만 return

이런 방식도 있다~

---

참고 - extra space 에 대한 제한이 없을 경우 간단하게 푸는 방법

Solution 3: Accepted (Runtime: 336 ms - 78.69% / Memory Usage: 25.1 MB - 22.85%)

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

1 ~ n 에서 중복 제거한 nums 빼주기