這題一開始看起來可以用 cyclic sort,但思考起來會卡在一個地方 - 如果是超過 array size 的 element 要放在哪邊?怎麼紀錄這些的順序性?
如果要把 4 放到對的位置,當前的 array size 是不夠的,所以就會有個兩難?我們需要去增加 array size 嗎?增加成 size 為 k 的 array 然後再做 cyclic sort?
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;
}
};