# 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/