In this Leetcode First Missing Positive problem solution we have given an unsorted integer array nums, return the smallest missing positive integer. You must implement an algorithm that runs in O(n) time and uses constant extra space.
Problem solution in Python.
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
if 1 not in nums:
return 1
a = nums.index(1)
for i in range(a+1, len(nums)):
if nums[i] - nums[i-1] > 1:
return nums[i-1] + 1
if i == len(nums)-1:
return nums[i] + 1
return 2
Problem solution in Java.
class Solution {
public int firstMissingPositive(int[] nums) {
Set<Integer> set = new HashSet<>();
int first = 1;
for (int num : nums) {
if (num > 0) {
set.add(num);
}
if (num == first) {
first++;
while (set.contains(first)) {
first++;
}
}
}
return first;
}
}
Problem solution in C++.
int firstMissingPositive(vector<int> a) {
int i,n=a.size();
for(i=0;i<n;i++)
if(a[i]<=0 || a[i]>n)
a[i] = INT_MAX;
a.push_back(INT_MAX);
for(i=0;i<n;i++)
{
if(abs(a[i])==INT_MAX) continue;
if(a[abs(a[i])]>0)
a[abs(a[i])] *= -1;
}
for(i=1;i<=n;i++)
if(a[i]>0)
break;
return i;
}
Problem solution in C.
int firstMissingPositive(int* nums, int numsSize){
int i = 0;
while (i < numsSize)
{
int n = nums[i];
/* Swap nums[i] to nums[nums[i] - 1] if possible */
if (0 < n && n < (numsSize + 1) && (n - 1) != i && nums[n - 1] != n)
{
nums[i] = nums[n - 1];
nums[n - 1] = n;
}
else
{
i++;
}
}
for (i = 1; i < numsSize + 1; i++)
{
if (nums[i - 1] != i)
break;
}
return i;
}