Python Bitarray solution

  • 0
    class Solution(object):
    def firstMissingPositive(self, nums):
        :type nums: List[int]
        :rtype: int
        if not nums:
            return 1
        n = len(nums)
        a = [0] * (n+1)
        a[0] = 1
        for x in nums:
            if x<=0 or x>n:
                a[x] = 1
        for i in range(n+1):
            if not a[i]:
                return i
        return n+1

    I know it may be not O(1) Space but it's still O(N) time. Leetcode can't import Bitarray so I used a list here to store 0,1. a[i] = 0 means positive integer i is not in the list.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.