problem

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

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

submission

impl Solution {
    pub fn first_missing_positive(mut nums: Vec<i32>) -> i32 {
        for i in 0..nums.len() {
            // cyclic sort
            // rotate nums[i] until it out of range or precisely i + 1
            while 0 < nums[i] && nums[i] <= nums.len() as i32
                    && nums[i] != nums[nums[i] as usize - 1] {
                let target = nums[i] as usize - 1;
                nums.swap(i, target);
            }
        }
        // iterate through rotated array to find the first missing positive
        nums.iter()
            .enumerate()
            .position(|(idx, &val)| idx as i32 + 1 != val)
            .unwrap_or(nums.len()) as i32 + 1
    }
}