41. First Missing Positive

我還以為我終於可以解難題了, 馬上被秒XD

首先我們先把每個數字, 交換到他應該在的位置

例如

[0, 1, 2]
我們會希望1可以放在對的位置, 就是array[0]的位置, 所以1跟0交換
[1, 0, 2]
2也是要放在對的位置, 2跟0在互換
[1,2,3]
接著遍歷index, 如果nums[index] != index+1, 那這個index + 1就是我們要得

太神拉, 這真的鬼

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