題目網址：https://leetcode.cn/problems/first-missing-positive/

題意：給一未排序的整數 array nums, 返回其中未出現的最小正整數。

必須設計 $O(n)$ time 且 $O(1)$ space 的演算法。

Solution 1：

想法：利用 hash table, 首先 hash table 儲存出現過的數, 然後再從 1 開始遍歷到 n。若其中有不在 hash table 中的, 則直接返回該數。否則, 返回 n + 1

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        const int n = nums.size();
        unordered_set<int> s(nums.begin(), nums.end());

        for (int i = 1; i <= n; ++i) {
            if (s.find(i) == s.end()) {
                return i;
            }
        }

        return n + 1;
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(n)$ ➔ umap, 並不符合題目要求

Solution 2：

想法：改進 Solution 1, 把 nums 本身當作 hash table 使用, 利用 nums[i] 判斷 i + 1 是否存在。若 i + 1 存在, 則 nums[i] == i + 1

  • 若 nums[i] 超出邊界, 或 nums[i] 已經放在正確的位置上, 則往下一個數
  • 否則, 用 swap 將 nums[i] 放在正確的位置上。可是 swap 完後, 不保證 idx = i 的位置擺的是正確的值, 因此要用 while loop 來確認, 直到 nums[i] == i + 1, 才能往下一個數

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        const int n = nums.size();

        for (int i = 0; i < n; ++i) {
            while (nums[i] != i + 1) {
                const int val = nums[i];

                // 若 val 不為範圍內之正整數 || val 已經放在 idx = val - 1 的位置上
                if (val <= 0 || val >= n || val == nums[val - 1]) {
                    break;
                } else { // 否則, 將其放在正確的位置上
                    swap(nums[i], nums[val - 1]); // 此時, 0 ≤ val < n, 不用取 abs
                }
            }
        }

        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        return n + 1;
    }
};
  • time：$O(n)$ ➔ for loop, 因為 while loop 中每個 idx 的位置最多做常數次
  • space：$O(1)$ ➔ 只需常數空間