Python O(n) another approach, no swap


  • 0

    the only three cases we have are:

    1. missing a number k that k < len(nums)
    2. missing len(nums)
    3. missing len(nums)+1

    so we first make every number in the list bigger than 0, then when we find each num in the list, we set nums[num] to be negative

    if we find a number is not negative in index i, then we are missing number i,
    or we are missing len(nums), simply check it,
    or we are missing len(nums)+1

    class Solution(object):
        def firstMissingPositive(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if not nums: return 1
            
            # make every number positive
            minN = min(nums)
            comp = 0
            if minN <= 0:
                comp = abs(minN) + 1
                for i in range(len(nums)):
                    nums[i] += comp
            
            # set indexed number to negative
            for i in range(len(nums)):
                n = abs(nums[i])
                if n - comp < len(nums) and n - comp >= 0:
                    if nums[n-comp] > 0:
                        nums[n-comp] = - nums[n-comp]
    
            # find the first missing index and if len(nums) is in nums
            alreadyL = 0
            l = len(nums) + comp
            for i in range(1, len(nums)):
                if nums[i] > 0:
                    return i
                elif abs(nums[i]) == l:
                    alreadyL = 1
               
            # return     
            if alreadyL or nums[0] == l:
                return len(nums) + 1
            return len(nums)
    
    
    

Log in to reply
 

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