題目描述
給定一個范圍在 1 ≤ a[i] ≤ n ( n = 數組大小 ) 的 整型數組米酬，數組中的元素一些出現(xiàn)了兩次异雁，另一些只出現(xiàn)一次另假。
找到所有在 [1, n] 范圍之間沒有出現(xiàn)在數組中的數字础淤。
您能在不使用額外空間且時間復雜度為O(n)的情況下完成這個任務嗎? 你可以假定返回的數組不算在額外空間內莹捡。
示例 1:
輸入:
[4,3,2,7,8,2,3,1]
輸出:
[5,6]
解法
若按序不重復存放鬼吵，則 n 個元素剛好存放于大小為 n 的數組中，即每個下標 i 處存放元素值為 i+1篮赢。
根據題目中描述齿椅，數組中可能存在重復元素，且并未按序存放荷逞。所以不妨遍歷數組媒咳，將每個元素調整到對應下標的位置，即將元素 k 存儲于下標為 k-1 處种远。然后遍歷數組涩澡，元素值與下標不匹配的即為消失元素數字。
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
ret=[]
for i in range(len(nums)):
c=nums[i]
while i+1!=c and nums[c-1]!=c:
nums[c-1],c,i=c,nums[c-1],c-1
return [i+1 for i in range(len(nums)) if nums[i]!=i+1]
