41. First Missing Positive
1. Description
Given an unsorted integer array nums, find the smallest missing positive integer.
2. Follow Up
Could you implement an algorithm that runs in O(n) time and uses constant extra space.?
3. Example
Example 1:
Input: nums = [1,2,0]
Output: 3
Example 2:
Input: nums = [3,4,-1,1]
Output: 2
Example 3:
Input: nums = [7,8,9,11,12]
Output: 1
4. Constraints
- 0 <= nums.length <= 300
- $-2^{31}$ <= nums[i] <= $2^{31}$ - 1
5. Solutions
My Accepted Solution(Follow Up)
n = m_nums.size() Time complexity: O(n) Space complexity: O(1)
class Solution
{
public:
// int firstMissingPositive(vector<int>& nums)
int firstMissingPositive(vector<int> &m_nums)
{
// the most optimal and valid array is {1, 2, 3, 4, 5, 6, ...}
// we try to convert to this kind of array, when we face a invalid number, this number is the missing number
// during this process, we convert all invalid number to 0
for(int i = 0; i < m_nums.size(); i++)
{
if(m_nums[i] == i + 1) continue; // valid number, we don't need to do anything
if(0 < m_nums[i] && m_nums[i] <= m_nums.size()) // the number is in the valid range
{
if(m_nums[m_nums[i] - 1] == m_nums[i]) // the correct place already has correct number, this number is useless
{
m_nums[i] = 0;
}
else // we swap the correct number to the correct place
{
swap(m_nums[m_nums[i] - 1], m_nums[i]);
i--; // we need to check whether the exchanged number is valid, so we decrease i, since it will increase automatically
}
}
else // this number is not in the valid range, so it is useless for us to build an optimal array
{
m_nums[i] = 0;
}
}
for(int i = 0; i < m_nums.size(); i++)
{
if(m_nums[i] == 0) return i + 1;
}
return m_nums.size() + 1;
}
};