41. First Missing Positive

Jul 6th, 2022
746
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. '''
2. Given an unsorted integer array nums, return the smallest missing positive integer.
3. You must implement an algorithm that runs in O(n) time and uses constant extra space.
4. '''
5. class Solution:
6.     def firstMissingPositive(self, nums: List[int]) -> int:
7.         n=len(nums)
8.         mval=max(nums)
9.         for i in range(n):
10.             if nums[i]<=0:
11.                 nums[i]=float('inf')
12.
13.         for i,j in enumerate(nums):
14.             j=abs(j)
15.             if 0<j<=n and nums[j-1]>0:
16.                 nums[j-1]=-1*nums[j-1]
17.
18.
19.         for i in range(1,n+1):
20.             if nums[i-1]>0:return i
21.         else:
22.             return n+1
23. '''
24. Basic idea:
25.    1. for any array whose length is l, the first missing positive must be in range [1,...,l+1],
26.        so we only have to care about those elements in this range and remove the rest.
27.    2. we can use the array index as the hash to restore the frequency of each number within
28.         the range [1,...,l+1]
29. '''
30.