問題描述：

給定一個范圍在? 1 ≤ a[i] ≤ n (?n = 數組大小 ) 的 整型數組，數組中的元素一些出現了兩次，另一些只出現一次。

找到所有在 [1, n] 范圍之間沒有出現在數組中的數字。

您能在不使用額外空間且時間復雜度為O(n)的情況下完成這個任務嗎? 你可以假定返回的數組不算在額外空間內。

示例:

輸入:

[4,3,2,7,8,2,3,1]

輸出:

[5,6]

核心;循環排序法，讓每個數字在其應該的位置上。注意數值和下標之間的關系

classSolution:def findDisappearedNumbers(self, nums: List[int]) ->List[int]:

res=[]

l=0

r=len(nums)-1

while l<=r:if nums[l] != nums[nums[l]-1]:

nums[nums[l]-1],nums[l] = nums[l],nums[nums[l]-1]else:

l+=1

for i inrange(len(nums)):if i+1 !=nums[i]:

res.append(i+1)return res

比如：nums=[4,3,2,7,8,2,3,1]

過程：

[7,3,2,4,8,2,3,1]

[3,3,2,4,8,2,7,1]

[2,3,3,4,8,2,7,1]

[3,2,3,4,8,2,7,1]

[2,3,3,4,8,2,7,1]

[2,3,3,4,1,2,7,8]

[1,3,3,4,2,2,7,8]

[1,2,3,4,3,2,7,8]

最后再遍歷一次數組：值!=下標+1，將下標+1加入到結果中。

結果：

原文：https://www.cnblogs.com/xiximayou/p/12358903.html