LeetCode 解题报告 (41)-- 第一个缺失的正整数

发表于 标签

原题如下：

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.

题目要求找出第一个缺失的正整数，难点在于时间复杂度要控制在 O (n)，也就是说不能对数组排序，空间复杂度要控制在 O (1)，也就是说不能开一个新的数组去存储这些数字。

但是这道题目也有它的特点，假如给定的数组的长度为 n，那么缺失的第一个正数肯定在 [1,n+1] 内，根据这个特点，可以将范围为 [1,n] 的数字移动到与其数值相等的下标的位置，对所有的数这样操作后从头遍历一遍数组，找出的第一个 i+1 != a[i] 的 i, 那么 i+1 就是第一个缺失的正整数。

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 xrange(n):
            while 0<nums[i]<=n and (not nums[nums[i]-1]==nums[i]):
                    tmp = nums[i]
                    nums[i] = nums[tmp-1]
                    nums[tmp-1] = tmp
                    # nums[i],nums[nums[i]-1] = nums[nums[i]-1],nums[i]错误

        for i in xrange(n):
            if nums[i] == i+1:
                continue
            else:
                return i+1

        return n+1 # all match