leetcode41解法

2018-04-28

详细题目见41. First Missing Positive

Problem

为给定一个整数数组，求其缺少的最小正整数。

时间复杂度限制为O(n)，空间复杂度限制为O(1)。

Example 1:

1 2	Input: [1,2,0] Output: 3

Example 2:

1 2	Input: [3,4,-1,1] Output: 2

Solution

思路是遍历一遍数组把所有正整数丢到对应的桶里（类似桶排），比如1丢到第1个位置，8丢到第8个位置，考虑到要使用常数阶的空间，因此可以用一个整数的每一位来表示一个数的有无（0表示有，1表示没有）。

PS：这里即使是用整数似乎也并不算是常数阶的空间复杂度？1个整数只能存放32个数（针对别的语言），python官方说对整数实现了无穷的范围，故这里只用一个整数就可以表示所有的整数有无。

代码

class Solution:
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        x = 0
        for each in nums:
            x |= int(2**each)
        cnt = 1
        x >>= 1
        while x % 2:
            cnt += 1
            x >>= 1
        return cnt

第一个for将数存放到x的相应位中，不需要特别判断，因为负数的话计算出来是0（取整后），0的话计算出来是1，等会在循环外移1次位即可。

第二个循环找到从低位开始的第一个0。整体时间复杂度为O(n)。