Python solution


  • 0
    F
    import sys
    class Solution:
    
        def firstMissingPositive(self, nums):
            if len(nums) == 0:  return 1
    
            for r in nums:     # remove non_positive  in nums in O(n)
                if r <= 0:
                    nums.remove(r)
    
            res = sys.maxint
            for i in range(1,len(nums)+1):  # find missing positive in nums in O(n)
                if i not in nums and i < res:
                    res = i
    
            if res == sys.maxint:
                return len(nums)+1
            return res

  • -1
    S

    Both places where you claim O(n) are O(n^2) because list.remove is O(n), and x in list is O(n), see https://wiki.python.org/moin/TimeComplexity.


Log in to reply
 

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