41. 缺失的第一個正數

先是有對題目的分析，才用雙指針實現它

思路

題目額外要求時間複雜度 $O(n)$ ，空間複雜度 $O(1)$ 。假設現在數組如下

要求缺失的第一個正數，對於大小為 10 的數組來說，最佳的情況，就是包含 $1\sim10$ 的所有數字。
對於位置 $0$ 來說，應該要把數字 $1$ 放在這裡 $\to$ 對於位置 $i$ 來說，應該要把 $i+1$ 放在這裡。

創建兩個指針left = 0，right = 9，分情況討論，指針的移動規則如下，從上往下順著判斷：
left左邊的所有位置都是擺放正確的，而right右邊放著多餘的，不需要的數值。

1. nums[left] == left + 1
   • 符合期望，left++。
2. nums[left] <= left
   • 不符合期望，right--，交換nums[left], nums[right]。
3. nums[left] > right
   • 不符合期望，right--，交換nums[left], nums[right]。
4. nums[nums[left] - 1] == nums[left]
   • 雖然是範圍內的數字，但是目標位置已經有正確的數字擺放，這個數字是多餘的，right--，交換nums[left], nums[right]，
5. nums[nums[left] - 1] != nums[left]
   • 沒有正確的數字擺放，這個數字要交換到正確的位置上，交換nums[left], nums[nums[left] - 1]。

※ 條件二三是相同的，都是遇到了預期範圍之外的數字。

詳細流程

1. 滿足第二個條件，right--，交換nums[left], nums[right]。 $-3$ 是一個沒有落在期望範圍 $1\sim10$ 的數字，因為多了一個無用的數字，所以期望範圍縮減成 $1\sim9$ 。

2. 滿足第一個條件，交換nums[left], nums[right]，right--， 多了一個無用數字 $13$ ，期望範圍縮減， $1\sim8$ 。

3. 滿足第四個條件，出現的數字在期望範圍內，但是對應的位置已經放了正確的數字（藍色標記），所以當前的數字無用，交換nums[left], nums[right]，right--，期望範圍縮減， $1\sim7$ 。

4. 滿足第五個條件，出現的數字在期望範圍內，而且對應的位置沒有正確數字，交換到正確位置上面。

5. 連續三次滿足第一個條件，數字都在正確的位置上，移動左指針，此時期望範圍 $4\sim7$

6. 滿足第三個條件，出現的數字在範圍外，交換nums[left], nums[right]，right--， 期望範圍縮減， $4\sim6$ 。

7. 滿足第二個條件，出現的數字在範圍外，交換nums[left], nums[right]，right--， 期望範圍縮減， $4\sim5$ 。

8. 連續兩次滿足第一個條件，移動左指針，此時兩指針重疊，最後的答案是left + 1(5+1)。

程式碼

雙指針

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        int left = 0, right = n; // 左閉右開
        while(left < right) {
            if(nums[left] == left + 1) {
                left++;
            }
            // 條件二三四
            else if(nums[left] <= left || nums[left] > right || nums[nums[left] - 1] == nums[left]) {
                swap(nums[left], nums[--right]);
            }
            else {
                swap(nums[left], nums[nums[left] - 1]);
            }
        }
        return left + 1;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$