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