Leetcode 41 - Loading...
The beauty of the solution lies in using the sign bit to optimize for the space constraint.
class Solution {
public int firstMissingPositive(int[] nums) {
boolean has1 = false;
for (int n: nums) if (n == 1) { has1 = true; break; };
if (!has1) return 1;
for (int i=0; i<nums.length; i++)
{
if (nums[i] <= 0 || nums[i] > nums.length)
nums[i] = 1;
}
for (int i=0; i<nums.length; i++)
{
int place = Math.abs(nums[i]);
if (nums[place-1] > 0)
nums[place-1] = -nums[place-1];
}
for (int i=0; i<nums.length; i++)
{
if (nums[i] > 0) return i+1;
}
return nums.length+1;
}
}