First Missing Positive
Problem
Given an unsorted integer array of length , return the smallest missing positive integer.
You must implement an algorithm that runs in time and uses auxiliary space.
Example
Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.
Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.
Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.
Constraints
Submit your solution at here
Solution
Intuition
Sort and find missing element resulting in time, so that solution would AC if you insist on doing so 🙄. We can do better than that. We will traverse once and fill all number slots. Then do a 2nd pass and check for the first unfilled slot.
Approach
We define “useless” number as a number that is not contribute to our final sequence. Those number are
- Out of range
- Or already exist before
For example:
[3,4,-1,1,0,99] // -1, 0, 99 are useless number
[7,8,9,11,12] // all numbers in the array are out of range [1~5] and are useless
In the first pass, we will have a running pivot , and put all useful number in its position, all useless number behind For example, this is an array before/after first pass
// input array
[0,6,2,2,4,0,1,4,1,3]
// loop iteration
check 10
swap 10/3, nums = [0, 6, (3), 2, 4, 0, 1, 4, 1, (2)]
check 10
swap 10/2, nums = [0, (2), 3, 2, 4, 0, 1, 4, 1, (6)]
check 10
swap 10/6, nums = [0, 2, 3, 2, 4, (6), 1, 4, 1, (0)]
check 10 nothing happened
check 9
swap 9/1, nums = [(1), 2, 3, 2, 4, 6, 1, 4, (0), 0]
check 9 nothing happened
check 8
swap 8/4, nums = [1, 2, 3, (4), 4, 6, 1, (2), 0, 0]
check 8~1 nothing happened
In the final array, notice that first position has an odd item is , so we return
Complexity
- Time complexity:
- Space complexity:
Code
impl Solution {
pub fn first_missing_positive(nums: Vec<i32>) -> i32 {
let mut nums = nums;
let mut i = nums.len();
while i > 0 {
let useless = nums[i-1] > i as i32 || nums[i-1] < 1;
if useless {
i -= 1;
continue;
}
let j = nums[i-1] as usize;
let useless = nums[i-1] == nums[j-1];
if useless {
i -= 1;
continue;
}
nums.swap(i-1,j-1);
}
//println!("{:?}", nums);
return nums.iter()
.enumerate()
.take_while(|&(i, &x)| i as i32 == x-1)
.count() as i32 + 1;
}
}