This is a Leetcode problem:
Given an unsorted integer array, find the smallest missing positive integer.
Your algorithm should run in O(n) time and uses constant extra space.
Here is my first solution to this problem:
class Solution: def __init__(self, A): self.A = A def firstMissingPositive(self, A): #Get rid of non-positive elements for n in A: if n <= 0: A.remove(n) if A == : return 1 maximum = max(A) res =  * maximum for n in A: if n > 0: res[n - 1] = 1 for i in range(len(res)): if res[i] == 0: return i + 1 return maximum + 1 A = #Enter a list. missing_integer = Solution(A) print(missing_integer.firstMissingPositive(A))
Here are the inputs/outputs for my program. They have the same outputs as the examples given in the challenge here:
A = [1,2,0] >>> 3 A = [3,4,-1,1] >>> 2 A = [7,8,9,11,12] >>> 1
Here is my second solution to this problem:
# O(n) time def firstMissingPositive(nums): for i in range(len(nums)): while 0 <= nums[i] - 1 < len(nums) and nums[nums[i]-1] != nums[i]: tmp = nums[i] - 1 nums[i], nums[tmp] = nums[tmp], nums[i] for i in range(len(nums)): if nums[i] != i + 1: return i + 1 return len(nums) + 1 nums = #Enter a list. print(firstMissingPositive(nums))
Inputs/outputs - Same as above.
So, I would like to have a code review for the efficiency of both the solutions.
Any help would be highly appreciated.