leetcode/
first_missing_positive.rs

1//! # 41. 缺失的第一个正数
2//!
3//! 难度 困难
4//!
5//! 给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
6//!
7//!
8//!
9//! ## 示例 1:
10//!
11//! ```text
12//! 输入: [1,2,0]
13//! 输出: 3
14//! ```
15//!
16//! ## 示例 2:
17//!
18//! ```text
19//! 输入: [3,4,-1,1]
20//! 输出: 2
21//! ```
22//!
23//! ## 示例 3:
24//!
25//! ```text
26//! 输入: [7,8,9,11,12]
27//! 输出: 1
28//! ```
29//!
30//! See [leetcode](https://leetcode-cn.com/problems/first-missing-positive/)
31
32pub struct Solution;
33
34impl Solution {
35    pub fn first_missing_positive(nums: Vec<i32>) -> i32 {
36        let mut nums = nums;
37        let len = nums.len() as i32;
38        for i in 0..nums.len() {
39            while nums[i] > 0 && nums[i] <= len && nums[nums[i] as usize - 1] != nums[i] {
40                let v = nums[i] as usize - 1;
41                nums.swap(i, v);
42            }
43        }
44
45        for i in 0..nums.len() {
46            if nums[i] != i as i32 + 1 {
47                return i as i32 + 1;
48            }
49        }
50        return len + 1;
51    }
52}
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57
58    #[test]
59    fn test() {
60        let t = |n| Solution::first_missing_positive(n);
61        assert_eq!(3, t(vec![1,2,0]));
62        assert_eq!(2, t(vec![3,4,-1,1]));
63        assert_eq!(1, t(vec![7,8,9,11,12]));
64        assert_eq!(6, t(vec![1,2,3,4,5]));
65    }
66}
leetcode/first_missing_positive.rs

leetcode/
first_missing_positive.rs
