LeetCode 41. First Missing Positive [Hard] [C++] 解題筆記

Given an unsorted integer array, find the smallest missing positive integer.

EX:

        Input: [1,2,0]

        Output: 3

        Input: [3,4,-1,1]

        Output: 2

        Input: [7,8,9,11,12]

        Output: 1

想法:

        這題題目要求在 O(n) 時間且O(1) 空間的限制下完成。這題其實有點類似排序題，要找到 smallest missing

positive integer 換言之就必須知道順序，因此其實這題的重點就在於排序，一般排序的方式都需要 O(nlogn) 時間

才能達到，但這題有個重點是我們不在意負數因此我可以遍歷一次 array 然後將 元素 i 放在第 i - 1 個位置上，

例如 index 0 -> 1, index 1 -> 2 依此類推，最後只須要再重新遍歷一次 array 如果遇到 nums[i] != i + 1 的話表示 i + 1 即是

答案，若遍歷完成且 nums[i] = i + 1 對整個 array 接成立，則答案為 nums.size() + 1。

完整程式碼:

Complexity: O(nlogn) time，O(n) space

解法一(HashMap/Sort):

class Solution {

public:

    int firstMissingPositive(vector<int>& nums) {

        if (nums.empty()) { return 1; }

        set<int> s(nums.begin(), nums.end());

        if (*s.rbegin() < 0) { return 1; }

        for (int i = 1; i <= *s.rbegin(); i++) {

            if (find(s.begin(), s.end(), i) == s.end()) { return i; }

        }

        return *s.rbegin() + 1;

    }

};

Complexity: O(n) time, O(1) space

解法二:

class Solution {

public:

    int firstMissingPositive(vector<int>& nums) {

        for (int i = 0; i < nums.size(); i++) {

            // put all element i in index i - 1 position

    while (nums[i] > 0 && nums[i] <= nums.size() && nums[nums[i] - 1] != nums[i]) {

                swap(nums[i], nums[nums[i] - 1]);

            }

        }

        for (int i = 0; i < nums.size(); i++) {

            if (nums[i] != i + 1) { 

                cout<<i<<endl;

                return i + 1; }

        }     

        return nums.size() + 1;

    }

};