English
41. First Missing Positive 
Problem Statement
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 O(1) auxiliary space.
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
Click to open Hints
- Think about how you would solve the problem in non-constant space. Can you apply that logic to the existing space?
- We don't care about duplicates or non-positive integers
- Remember that O(2n) = O(n)
Solution:
go
package main
func firstMissingPositive(nums []int) int {
i := 0
for i < len(nums) {
if nums[i] > 0 && nums[i] <= len(nums) && nums[nums[i]-1] != nums[i] {
nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
} else {
i++
}
}
for i, num := range nums {
if num != i+1 {
return i + 1
}
}
return len(nums) + 1
}
rs
impl Solution {
pub fn first_missing_positive(nums: Vec<i32>) -> i32 {
let (mut nums, mut i) = (nums, 0);
while i < nums.len() {
let num = nums[i];
// if the number is in the range [1, nums.len()] and not in the right position
// swap it with the number at the right position
if num > 0 && num <= nums.len() as i32 && num != nums[num as usize - 1] {
nums.swap(i, num as usize - 1);
} else {
i += 1;
}
}
// find the first missing positive number
for (i, num) in nums.iter().enumerate() {
if num != &(i as i32 + 1) {
return i as i32 + 1;
}
}
nums.len() as i32 + 1
}
}
...