class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
}
};
41. 缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0] 输出：3
示例 2：
输入：nums = [3,4,-1,1] 输出：2
示例 3：
输入：nums = [7,8,9,11,12] 输出：1
提示：
1 <= nums.length <= 5 * 105-231 <= nums[i] <= 231 - 1原站题解
python3 解法, 执行用时: 60 ms, 内存消耗: 20.2 MB, 提交时间: 2022-08-20 11:58:58
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1
python3 解法, 执行用时: 64 ms, 内存消耗: 20.1 MB, 提交时间: 2022-08-20 11:55:12
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n):
if nums[i] <= 0:
nums[i] = n + 1
for i in range(n):
num = abs(nums[i])
if num <= n:
nums[num - 1] = -abs(nums[num - 1])
for i in range(n):
if nums[i] > 0:
return i + 1
return n + 1
python3 解法, 执行用时: 36 ms, 内存消耗: 13.3 MB, 提交时间: 2020-09-09 23:00:38
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
res = 1
if len(nums) == 0:
return res
max_, min_ = max(nums), min(nums)
if max_ < res or min_ > res:
return res
for i in range(1, max_):
if i not in nums:
return i
return max_ + 1