未排序整數數組,找出最小的缺失正整數。要求 O(n) 時間、O(1) 額外空間。
例:[1,2,0]→3, [3,4,-1,1]→2。
利用數組下標作為「鍵」:將值為 x 的元素放到下標 x-1 的位置(即 nums[x-1] = x)。遍歷數組,對每個位置 i,只要 nums[i] 在 [1, n] 範圍內且不在正確位置(nums[nums[i]-1] != nums[i]),就交換 nums[i] 和 nums[nums[i]-1]。交換後新來的 nums[i] 可能仍需歸位,故 i-- 重新檢查。
最終再次遍歷,第一個 nums[i] != i+1 的位置 i,答案為 i+1。若全對應,答案為 n+1。