# Find the First K Missing Positive Numbers

解法一 - Cyclic sort

這題一開始看起來可以用 cyclic sort,但思考起來會卡在一個地方 - 如果是超過 array size 的 element 要放在哪邊?怎麼紀錄這些的順序性?

比如說

[-2, -3, 4]

如果要把 4 放到對的位置,當前的 array size 是不夠的,所以就會有個兩難?我們需要去增加 array size 嗎?增加成 size 為 k 的 array 然後再做 cyclic sort?

以上當然是一種可行的做法,而另外一種做法就是使用 Hash Set 儲存是 positive integer 但多出來的,這樣就不需要把 array 變長。

using namespace std;

#include <iostream>
#include <unordered_set>
#include <vector>

class FirstKMissingPositive {
 public:
  static vector<int> findNumbers(vector<int> &nums, int k) {
    // Cyclic sort
    int i = 0, n = nums.size();
    while(i < n) {
      int j = nums[i] - 1;
      if(j >= 0 && j < n && nums[i] != nums[j]) {
        swap(nums[i], nums[j]);
      }
      else {
        ++i;
      }
    }

    //Add the missing number in current indexes
    vector<int> missingNumbers;
    unordered_set<int> excessNumber;
    for(int i = 0; i < n && missingNumbers.size() < k; ++i) {
      if(nums[i] != i + 1) {
        missingNumbers.push_back(i + 1);
        excessNumber.insert(nums[i]);
      }
    }

    // Add the remaining missing number
    for(int i = 1; missingNumbers.size() < k; ++i) {
      if(!excessNumber.count(n + i)) {
        missingNumbers.push_back(n + i);
      }
    }

    return missingNumbers;
  }
};

Last updated