首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> 關於C++

LeetCode 41 First Missing Positive:原地哈希 O(n) 時間 O(1) 空間

     編輯:關於C++

題目大意

未排序整數數組,找出最小的缺失正整數。要求 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。

C++ 實現

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved