題目:

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.

給定一長度為n的陣列nums,其元素值的範疇在1~n
找出1~n所有不在nums內的元素,放在一陣列內回傳

我採取最直觀的做法

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

設立一個nums的set(numset),接著一個一個確認1~n的值是否在numset內
不在就放入ans內,最後回傳ans
最後執行時間365ms(faster than 91.74%)

說實在的,這其實是在找nums和range(1,len(nums)+1)兩set的差集

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

於是我們直接將兩set相減回傳
最後執行時間360ms(faster than 93.16%)

題目隨後提出一個挑戰

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

題目要求我們寫出不用額外記憶體且複雜度為O(n)的解
我沒有頭緒,但我在討論區看到一個堪稱巧妙的解法如下

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

根據題目的敘述,我們可以知道nums是不會有負數的
這個解法就是運用這一點結合index來記錄出現過的值

一開始先遍歷一次nums
將index為abs(出現的值)-1的值加上一個負號,紀錄出現的值的存在
加上我們有套絕對值,所以不用擔心因為更動漏看值

接著我們再遍歷一次nums,發現正數時
表示該正數的index+1不在nums內
將index+1放入ans,最後回傳ans
最後執行時間397ms(faster than 83.43%)

今天比較忙,更一題就好

那我們下題見