First Missing Positive LeetCode上的41题：https://leetcode-cn.com/problems/first-missing-positive/description/ First Missing Positive 题目题解代码 题目 Given an unsorted integer array, find the small

这道题写的时候完全没有思路，看了很久的题解，才总结出来。 class Solution:def firstMissingPositive(self, nums: List[int]) -> int:nums_set = set(nums)n = len(nums)for i in range(1, n + 1):if i not in nums_set:return ireturn n + 1

文章目录 一、题目二、题解 一、题目 Given an unsorted integer array nums, return the smallest missing positive integer. You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

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

思路：原地哈希表 长度为N的数组，没有出现过的正整数一定是1~N+1中的一个。 此时会思考能不能用一个哈希表来保存出现过的1~N+1的数，然后从 1 开始依次枚举正整数，并判断其是否在哈希表中 但是题目要求常数级别的空间，就不能使用N的哈希表了。 这里将原数组当做哈希表，使用标记的办法来标记出现过的正整数，最后遍历数组，第一个没出现的下标+1就是答案 怎么样进行标记呢？ 先遍历一

Given an unsorted integer array, find the first missing positive integer. For example, Given [1,2,0] return 3, and [3,4,-1,1] return 2. Your algorithm should run in O(n) time and uses constant sp