source: https://leetcode.com/problems/first-missing-positive/
C/C++ Solution to LeetCode problem 41. First Missing Positive.
Problem
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.
Examples
Example 1:
Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.
Example 2:
Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.
Example 3:
Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.
Constraints
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
Solution
- Because we are looking for a positive integer, we can “remove” all the negative numbers (We set them to
0
). - If we have an array of size
n
with numbersfrom 2 to n+1
we know that the value missing is1
; if the array has all the values[1,n]
, then the first missing integer isn+1
. So, we are looking for an integer in the range[1, n+1]
. - For each number, we verify if its absolute is a number in the range
[1,n]
. - If so, we can verify the value present at the index that should be for that number if the array was sorted (with values from
1 to n
).- If the value at that position is
> 0
, we mark them as negative. - If the value is
0
we set it to-(n+1)
.
- If the value at that position is
- Once completed, we iterate through the array, and the first element with value
>0
that’s the missing integer (index+1
).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n=nums.size();
for (int i=0;i<n;++i)
if (nums[i]<0) nums[i] = 0;
for (int i=0;i<n;++i){
int absv = abs(nums[i]);
if (absv >= 1 && absv <= n) {
if (nums[absv-1] > 0)
nums[absv-1] *= -1;
else if (nums[absv-1] == 0)
nums[absv-1] = -1*(n+1);
}
}
for (int i=1;i<n+1;++i)
if (nums[i-1]>=0) return i;
return n+1;
}
};