C++實現LeetCode(41.首個缺失的正數)

Posted on by

[LeetCode] 41. First Missing Positive 首個缺失的正數

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

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

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

Example 3:

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

Note:

Your algorithm should run in O(n) time and uses constant extra space.

這道題讓我們找缺失的首個正數，由於限定瞭 O(n) 的時間，所以一般的排序方法都不能用，最開始博主沒有看到還限制瞭空間復雜度，所以想到瞭用 HashSet 來解，這個思路很簡單，把所有的數都存入 HashSet 中，然後循環從1開始遞增找數字，哪個數字找不到就返回哪個數字，如果一直找到瞭最大的數字（這裡是 nums 數組的長度），則加1後返回結果 res，參見代碼如下：

解法一：

// NOT constant space
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_set<int> st(nums.begin(), nums.end());
        int res = 1, n = nums.size();
        while (res <= n) {
            if (!st.count(res)) return res;
            ++res;
        }
        return res;
    }
};

但是上面的解法不是 O(1) 的空間復雜度，所以需要另想一種解法，既然不能建立新的數組，那麼隻能覆蓋原有數組，思路是把1放在數組第一個位置 nums[0]，2放在第二個位置 nums[1]，即需要把 nums[i] 放在 nums[nums[i] – 1]上，遍歷整個數組，如果 nums[i] != i + 1, 而 nums[i] 為整數且不大於n，另外 nums[i] 不等於 nums[nums[i] – 1] 的話，將兩者位置調換，如果不滿足上述條件直接跳過，最後再遍歷一遍數組，如果對應位置上的數不正確則返回正確的數，參見代碼如下：

解法二：

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }
};

到此這篇關於C++實現LeetCode(41.首個缺失的正數)的文章就介紹到這瞭,更多相關C++實現首個缺失的正數內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：