当前位置 博文首页 > Keep Coding:LeetCode-Python-41. 缺失的第一个正数
给定一个未排序的整数数组,找出其中没有出现的最小的正整数。
示例?1:
输入: [1,2,0] 输出: 3
示例?2:
输入: [3,4,-1,1] 输出: 2
示例?3:
输入: [7,8,9,11,12] 输出: 1
说明:
你的算法的时间复杂度应为O(n),并且只能使用常数级别的空间。
思路:
对于处于1~n之间的数,把它们放到nums[i - 1]的位置上,
然后从前遍历看有没有值不等于下标加一的元素,第一个这样的元素的下标+1就是答案。
如果没有就说明当前的数字刚好覆盖了1~n, n是nums的长度。
class Solution(object):
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for i in range(len(nums)):
while 1 <= nums[i] <= len(nums) and nums[i] != nums[nums[i] - 1]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
for i, x in enumerate(nums):
if x != i + 1:
return i + 1
return len(nums) + 1
?
cs