LeetCode41 缺失的第一個正數

給你一個未排序的整數陣列，請你找出其中沒有出現的最小的正整數。

第一種方法，置換，把每個x放到x-1的位置上（減一是因為這裡是說正整數，如果不減一會沒法處理到0號位置的數）。這樣做完之後重新遍歷，第一個不等於位置x+1的數就是答案。

1

class
solution 9}
10for (int i = 0; i < n; ++i) 14}
15return n + 1;16
}17};18
leetcode-cn.com/problems/first-missing-positive/solution/que-shi-de-di-yi-ge-zheng-shu-by-leetcode-solution/
21第二種，原地雜湊。雜湊表可以直接處理這個問題，但是需要o(n)的額外空間。我們可以直接原地建立雜湊表。因為答案只可能在(1,n+1)的範圍內，所以可以原地雜湊。先把所有非正數變為n+1，然後遍歷陣列，遇到任何一個小於n+1的數，假如為x，就把x-1的位置的數置為負的。操作完畢後最後遍歷陣列，遇到的第一個不是負數的位置x，就返回x+1。如果沒有就返回n+1。
需要注意在第二次遍歷的時候，判斷出數字不是n+1後，應該把陣列先取出來取絕對值，否則會造成訪問負數位置，導致越界。
1class
solution 17}
18for (int i = 0; i < n; ++i) 
22return n+1;23
}24 };

Leetcode 41 缺失的第一個正數

給定一個未排序的整數陣列，找出其中沒有出現的最小的正整數。示例 1 輸入 1,2,0 輸出 3示例 2 輸入 3,4,1,1 輸出 2示例 3 輸入 7,8,9,11,12 輸出 1說明 你的演算法的時間複雜度應為o n 並且只能使用常數級別的空間。一開始建了一個flag陣列做的，發現好像並不能這麼...

LeetCode 41 缺失的第一個正數

思路真是巧妙啊 不得不讚，絕了 public int firstmissingpositive int a i 0 while i a.length a i i 1 i return i 1 private void swap int a,int i,int j 題目要求 用常數級別的額外空間，這個...

leetcode41 缺失的第一個正數

給定一個未排序的整數陣列，找出其中沒有出現的最小的正整數。示例 1 輸入 1,2,0 輸出 3 示例 2 輸入 3,4,1,1 輸出 2 示例 3 輸入 7,8,9,11,12 輸出 1 說明 你的演算法的時間複雜度應為o n 並且只能使用常數級別的空間。解這一題的核心思想就是將數放到其大小對應的索...