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.
- 桶排序，应该nums[i]存储i+1,若nums[i] += i+1, 则交换nums[i], nums[nums[i]-1]
(First-Missing-Positive.py) download
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 range(n):
while(nums[i] != i+1):
# 第三个条件是nums[i]要去的位置和现在的值相同，
if nums[i] < 0 or nums[i] >= n or nums[i] == nums[nums[i]-1]:
break
tmp = nums[i]
nums[i] = nums[tmp-1]
nums[tmp-1] = tmp
for i in range(n):
if nums[i] != i+1:
return i+1
# 所有的元素都在
return n+1
|