###### tags: `LeetCode` `Hard`
# LeetCode #41 [First Missing Positive](https://leetcode.com/problems/first-missing-positive)
### (Hard)
給你一個未排序的整數數組 nums ，請你找出其中沒有出現的最小的正整數。
請你實現時間複雜度為 O(n) 並且只使用常數級別額外空間的解決方案。

---
先將nums進行桶排序, nums[0]要裝1, nums[1]要裝2, nums[i]要裝i+1。 因此, 當nums[i]的值大於0且小於等於nums.size()同時不等於nums[nums[i]-1] (也就是i != nums[i]-1)。
(但可能會有重複值如[1,1],所以這邊寫nums[i]!=nums[nums[i]-1])

將nums[i]與nums[nums[i]-1]交換, 讓nums[i]回去原本它該在的位置, 也就是nums[nums[i]-1]。而單次迴圈的中止條件為nums[i]存的值的確為i+1。
桶排列完成後只要遍歷一次nums, 找出哪一個nums[i]的值不為i+1即為答案, 若迴圈跑完都正確則回傳nums.size()+1。若nums.size()=0則回傳1。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        if(nums.size()){
            for(int i=0;i<nums.size();i++){
              while(nums[i]>0 && nums[i]<=nums.size() && nums[i]!=nums[nums[i]-1]){
                  int temp=nums[nums[i]-1];
                  nums[nums[i]-1]=nums[i];
                  nums[i]=temp;
                }
            }
            for(int i=0;i<nums.size();i++){
                if(nums[i]!=i+1){
                    return i+1;
                }
            }
            return nums.size()+1;
        }
        return 1;
    }
};

---