題目： LeetCode - 41. First Missing Positive

題目說明

給一個陣列，求從 1 開始的正整數哪個最先沒有出現在陣列中。

解題思路

先使用 Index Sort 將陣列排序好後從頭開始尋找即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int firstMissingPositive(vector<int>& nums)
    {
        nums.insert(begin(nums), 0);
        for(int i = 0; i < nums.size(); ++i)
            while(nums[i] != i && nums[i] > 0 && nums[i] < nums.size() && nums[i] != nums[nums[i]]) swap(nums[i], nums[nums[i]]);
        for(int i = 1; i < nums.size(); ++i) if(nums[i] != i) return i;
        return nums.size();
    }
};