LeetCode解题报告(41)--第一个缺失的正整数

原题如下:

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 space.

题目要求找出第一个缺失的正整数,难点在于时间复杂度要控制在O(n),也就是说不能对数组排序,空间复杂度要控制在O(1),也就是说不能开一个新的数组去存储这些数字。

但是这道题目也有它的特点,假如给定的数组的长度为n,那么缺失的第一个正数肯定在[1,n+1]内,根据这个特点,可以将范围为[1,n]的数字移动到与其数值相等的下标的位置,对所有的数这样操作后从头遍历一遍数组,找出的第一个 i+1 != a[i]的i,那么i+1就是第一个缺失的正整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""

n = len(nums)
for i in xrange(n):
while 0<nums[i]<=n and (not nums[nums[i]-1]==nums[i]):
tmp = nums[i]
nums[i] = nums[tmp-1]
nums[tmp-1] = tmp
# nums[i],nums[nums[i]-1] = nums[nums[i]-1],nums[i]错误

for i in xrange(n):
if nums[i] == i+1:
continue
else:
return i+1

return n+1 # all match