Subsets (Python)
Path Sum (Python)

First Missing Positive (Python)

kitt posted @ 2014年2月08日 16:51 in LeetCode , 2758 阅读

题目给出1到N的正整数,但是不全,里面也可能混着0和负整数,找出第一个缺失的正整数。要求时间O(N)空间固定,可使用原数组,通过交换元素使得A[i] = i + 1,第二次遍历时不满足A[i] = i + 1的就是要找的数。

class Solution:
    # @param A, a list of integers
    # @return an integer
    def firstMissingPositive(self, A):
        length = len(A)
        for i in xrange(length):
            while A[i] != i + 1:
                if A[i] <= 0 or A[i] > length or A[i] == A[A[i]-1]: break
                # swap A[i], A[A[i]-1]
                t = A[A[i]-1]; A[A[i]-1] = A[i]; A[i] = t
        for i in xrange(length):
            if A[i] != i + 1:
                return i + 1
        return length + 1

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter