文章目录

• 41. 缺失的第一个正数：
• • 样例 1：
  • 样例 2：
  • 样例 3：
  • 提示：
• 分析：
• 题解：
• • rust
  • go
  • c++
  • c
  • python
  • java

41. 缺失的第一个正数：

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

样例 1：

输入：nums = [1,2,0]输出：3

样例 2：

输入：nums = [3,4,-1,1]输出：2

样例 3：

输入：nums = [7,8,9,11,12]输出：1

提示：

• 1 <= nums.length <= 5 * 10⁵
• -2³¹ <= nums[i] <= 2³¹ - 1

分析：

• 面对这道算法题目，二当家的陷入了沉思。
• 想要实现这个算法的功能并不难，但是要求了时间复杂度和空间复杂度，相当于不允许用过多的内存资源的同时也不允许太慢。
• 好在没说参数空间不可以修改，不说就是默认，我们就用参数的空间。我们把在范围内的正数放在对应的位置，处理完一遍数组后，第二次遍历数组，对应位置数字不对的就是缺失的正数。

题解：

rust

impl Solution {pub fn first_missing_positive(mut nums: Vec) -> i32 {let n = nums.len();(0..n).for_each(|i| {while nums[i] > 0 && nums[i] <= n as i32 && nums[(nums[i] - 1) as usize] != nums[i] {let temp = nums[i];nums[i] = nums[(temp - 1) as usize];nums[(temp - 1) as usize] = temp;}});for i in 0..n {if nums[i] != i as i32 + 1 {return i as i32 + 1;}}return n as i32 + 1;}
}

go

func firstMissingPositive(nums []int) int {n := len(nums)for i := 0; i < n; i++ {for nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i] {nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]}}for i := 0; i < n; i++ {if nums[i] != i+1 {return i + 1}}return n + 1
}

c++

class Solution {
public:int firstMissingPositive(vector& nums) {int n = nums.size();for (int i = 0; i < n; ++i) {while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {swap(nums[nums[i] - 1], nums[i]);}}for (int i = 0; i < n; ++i) {if (nums[i] != i + 1) {return i + 1;}}return n + 1;}
};

c

int firstMissingPositive(int* nums, int numsSize){for (int i = 0; i < numsSize; ++i) {while (nums[i] > 0 && nums[i] <= numsSize &&nums[nums[i] - 1] != nums[i]) {int temp = nums[i];nums[i] = nums[temp - 1];nums[temp - 1] = temp;}}for (int i = 0; i < numsSize; ++i) {if (nums[i] != i + 1) {return i + 1;}}return numsSize + 1;
}

python

class Solution:def firstMissingPositive(self, nums: List[int]) -> int:n = len(nums)for i in range(n):while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]for i in range(n):if nums[i] != i + 1:return i + 1return n + 1

java

class Solution {public int firstMissingPositive(int[] nums) {int n = nums.length;for (int i = 0; i < n; ++i) {while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {int temp = nums[i];nums[i] = nums[temp - 1];nums[temp - 1] = temp;}}for (int i = 0; i < n; ++i) {if (nums[i] != i + 1) {return i + 1;}}return n + 1;}
}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~