# coding: utf-8

class Solution:

# @param A, a list of integers

# @return an integer

def firstMissingPositive(self, A):

# write your code here

'''

对于每个大于等于0的数放到对应的位置上，

返回第一个A[i] != i + 1的数。

'''

i = 0

while i < len(A):

if (A[i] >= len(A)) or (A[i] < 0):

i += 1 # 不符合条件的数不管！

elif A[i] != i + 1: # 对于不在对应位置的数要找到正确的位置

j = A[i]

if A[i] != A[j - 1]:

A[i], A[j - 1] = A[j - 1], A[i]

else:

i += 1

else:

i += 1

for i in xrange(0, len(A)):

if A[i] != (i + 1):

return i + 1

return len(A) + 1

# medium: http://lintcode.com/zh-cn/problem/first-missing-positive/