Python Bitarray solution


  • 0
    Q
    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:
                pass
            else:
                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.