def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
Basic idea:
1. for any array whose length is l, the first missing positive must be in range [1,...,l+1],
so we only have to care about those elements in this range and remove the rest.
2. we can use the array index as the hash to restore the frequency of each number within
the range [1,...,l+1]
"""
nums.append(0)
n = len(nums)
for i in range(len(nums)): #delete those useless elements
if nums[i]<0 or nums[i]>=n:
nums[i]=0
for i in range(len(nums)): #use the index as the hash to record the frequency of each number
nums[nums[i]%n]+=n
for i in range(1,len(nums)):
if nums[i]/n==0:
return i
return n
Python O(1) space, O(n) time solution with explanation



Great idea. Since Java doesn't have
append
, I just use a variable instead. A little bit dumb though.class Solution { public int firstMissingPositive(int[] nums) { if (nums == null  nums.length == 0) { return 1; } int len = nums.length + 1; for (int i = 0; i < nums.length; i++) { if (nums[i] < 0  nums[i] >= len) { nums[i] = 0; } } int s = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] % len == nums.length) { s += len; } else { nums[nums[i] % len] += len; } } for (int i = 1; i < nums.length; i++) { if (nums[i] < len) { return i; } } if (s < len) { return len  1; } return len; } }
