""
問題描述：
給定一個未排序的整數數組，找出其中沒有出現的最小的正整數。
示例 1:
輸入: [1,2,0]
輸出: 3
示例 2:
輸入: [3,4,-1,1]
輸出: 2
示例 3:
輸入: [7,8,9,11,12]
輸出: 1
說明:
你的算法的時間複雜度應為O(n)，並且只能使用常數級別的空間。
思路：
可以使用桶排序的方式，將一個正數放到它對應的（值 - 1）的下標上，然後可以對數組進行遍歷，當元素的值和它對應的下標不匹配時，即為缺失的第一個正數。
java代碼：
public int firstMissingPositive(int[] nums) {
if(null == nums || nums.length == 0){
return 1;
}
for(int i = 0; i< nums.length ; i ++){
while(nums[i] > 0 && nums[i] <= nums.length && nums[i] != i + 1){
int temp = nums[i];
nums[i] = nums[temp - 1];
nums[temp - 1] = temp;
if(nums[i] == temp){
break;
}
}
}
for(int i = 0; i < nums.length ; i ++){
if(nums[i] != i + 1){
return i + 1;
}
}
return nums[nums.length - 1] + 1;
}
相關推薦
'LeetCode算法第72題：編輯距離'
"問題描述：給定兩個單詞 word1 和 word2，計算出將 word1 轉換成 word2 所使用的最少操作數 。你可以對一個單詞進行如下三種操作：插入一個字符刪除一個字符替換一個字符示例 1:輸入: word1 = "horse", word2 = "ros"輸出: ...
'2019年互聯網人才招聘報告：Java吃香，算法工程師緊缺，頭條崛起'
"作者 | 八爪盒子責編 | 屠敏技術變革，人才驅動。當前互聯網的就業機會和風口在何處？在這篇文章中，我們將對 7 月份國內各個主流招聘網站發佈的384,0533 條互聯網招聘需求，其中在剔除銷售、行政等非常規互聯網職位以及非知名公司後的 7819 個在招職位進行全面分析，...
'GitHub Python項目推薦｜數據結構和算法必知必會的50個代碼實現'
"GitHub Python項目推薦|數據結構和算法必知必會的50個代碼實現項目熱度標星(star)：8860關注(watch)：486拷貝(fork)：2644貢獻人數：98 （貢獻人數很多哈）倉庫大小：1 MB最後更新：2019-08-17代碼提交活躍：開發語言主要語言...
'LeetCode算法第68題：文本左右對齊'
"問題描述：給定一個單詞數組和一個長度 maxWidth，重新排版單詞，使其成為每行恰好有 maxWidth 個字符，且左右兩端對齊的文本。你應該使用“貪心算法”來放置給定的單詞；也就是說，儘可能多地往每行中放置單詞。必要時可用空格 ' ' 填充，使得每行恰好有 maxWi...
'圖解算法第二彈：整數反轉'
"本題源自 LeetCode ，題號7。1.題目描述給出一個 32 位的有符號整數，你需要將這個整數中每位上的數字進行反轉。示例 1:輸入: 123輸出: 321示例 2:輸入: -123輸出: -321示例 3:輸入: 120輸出: 21注意:假設我們的環境只能存儲得下 ...
推薦中...