41. First Missing Positive

1.問題

2.想法

• 提問

  • 確認題意: 每個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.程式碼

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;
    }
};