# 41. First Missing Positive

## 1.問題

## 2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>

* 提問
  * 確認題意:  每個element是依照1, 2, 3, 4...的順序排列, 並找出沒有出現在應有的位置上
* function header, parameter
* test input
* 說明想法
  * 規則: 即A\[i]的值應該是i + 1, 而且A\[i]的值應該是A\[A\[i] - 1]
  * 因此我們可以確認A\[i]與A\[A\[i] - 1]是否相同, 若不同則swap, 最後確認每個位置的值是否是i + 1, 若都沒問題則返回length + 1
* 測試計算複雜度

## **3.程式碼** <a href="#id-3-cheng-shi" id="id-3-cheng-shi"></a>

```
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int size = nums.size(), i = 0;
        while (i < size) {
            if (nums[i] <= size &&
                nums[i] > 0 &&
                nums[i] != nums[nums[i] - 1]) {
                swap(nums, i, nums[i] - 1);
            } else {
                i++;
            }
        }
        
        for (i = 0; i < nums.size(); i++) {
            if (nums[i] != (i+1) ){
                return i+1;
            }
        }
        
        return size + 1;
    }
private:
    void swap(vector<int>& nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
};
```