LintCode Q189 First Missing Positive in Python

  • Jinhai ZHOU
  • 3 Minutes
  • 2016年12月19日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
# @param A, a list of integers
# @return an integer
def firstMissingPositive(self, A):
# write your code here
if len(A) == 0:
return 1
# use input array as cache
# make every A[i] = i + 1
# A[i] <=> A[A[i] - 1]
for i in xrange(len(A)):
while A[i] != i + 1 and A[i] > 0 and A[i] <= len(A) and A[i] != A[A[i] - 1]:
index = A[i]
A[i]= A[index - 1]
A[index -1] = index
for i in xrange(len(A)):
if A[i] != i + 1:
return i + 1
return len(A) + 1
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。