Python: Solution based on "287. Find the Duplicate Number"


  • 0
    Z
    class Solution(object):
        def firstMissingPositive(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            max_pos = len(nums)
            i = 0
            for n in nums:
                k = n
                while k<=max_pos and k>0 and k!=nums[k-1]:
                    temp = nums[k-1]
                    nums[k-1] = k
                    k = temp
            while i<max_pos:
                if nums[i] != (i+1):
                    break
                i += 1
            return i+1
    

    Explanation:

    1. scan each element of nums,
      if the element k is a positive number "in range" ( in range = this element k>0 and <= len(nums), then record this discovered positive number in nums by using:
      nums[k-1] = k
      Since nums[k-1] is replaced by the discovered k, we need to keep nums[k-1] in a temp variable, then using while loop to repeat the above operation.

    2. In the end, we can check whether one positive integer k exists by checking if nums[k-1] == k


Log in to reply
 

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