41. 缺失的第一个正数

为保证权益，题目请参考 41. 缺失的第一个正数(From LeetCode).

解决方案1

CPP

//
// Created by lenovo on 2020/6/27.
//
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


class Solution {
public:
    int firstMissingPositive(vector<int> &nums) {
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] <= 0) {
                nums[i] = nums.size() + 1;
            }
        }

        for (int i = 0; i < nums.size(); ++i) {
            if (abs(nums[i]) <= nums.size() && nums[abs(nums[i]) - 1] >0 ) {
                nums[abs(nums[i]) - 1] = -nums[abs(nums[i]) - 1];
            }
        }

        for (int i = 0; i < nums.size(); ++i) {
            if(nums[i] > 0){
                return i+1;
            }
        }

        return nums.size()+1;
    }
};

int main() {

    vector<int> ans;
//    ans.push_back(3);
//    ans.push_back(4);
    ans.push_back(1);
    ans.push_back(1);

    Solution so;
    cout << so.firstMissingPositive(ans) << endl;

    return 0;
}

Python

from typing import List


class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        inf = float('inf')
        for i in range(len(nums)):
            nums[i] = inf if nums[i] <= 0 else nums[i]

        for i in range(len(nums)):
            n = abs(nums[i])
            if n >= 1 and n <= len(nums):
                nums[n-1] = -abs(nums[n-1])

        for i in range(len(nums)):
            if nums[i] > 0:
                return i+1

        return len(nums) + 1


so = Solution()
print(so.firstMissingPositive([1, 1]))