2021-02-04 | 41. 缺失的第一个正数

1. 题目描述

给你一个未排序的整数数组 ​​nums​​ ，请你找出其中没有出现的最小的正整数。

进阶： 你可以实现时间复杂度为 ​​O(n)​​ 并且只使用常数级别额外空间的解决方案吗？

示例 1：

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

示例 2：

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

示例 3：

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

提示：

​​0 <= nums.length <= 300​​​​-2 <= nums[i] <= 2 - 1​​

2. 解题思路

对于这道题目，要求在O(n)的时间复杂度内完成，那我们就要在不影响原数组的基础上进行操作。

我们假设缺失的第一个正数是n，那么如果将这个数组按照从小到大排序完之后，1~n-1都应该排在n前面，比n大的数不会影响最后的结果。所以nums数组的长度最小就是n-1，即 n >= nums.length；我们可以遍历数组，对于大于1，并且小于nums.length - 1 的元素不用进行交换。在这个区间的元素交换到nums[i] - 1 的位置。简单来说就是将元素换到数组中第元素的值的位置。这样，最后如果当前数组中​​nums[i] != i + 1​​，就说明这个元素是缺失的元素。

示例2交换后的顺序如下：

复杂度分析：

时间复杂度：O(n)，其中n是数组的长度，需要遍历两次数组，第一次进行交换。第二次查找结果，时间复杂度为O(2n)；空间复杂度：O(1)，这里不需要额外的空间储存变量，所以空间复杂度为O(1)。

3. 代码实现

/** * @param {number[]} nums * @return {number} */var firstMissingPositive = function(nums) { const len = nums.length if(!len){ return 1 } for(let i = 0; i < len; i++){ while(nums[i] >= 1 && nums[i] <= len && nums[nums[i] - 1] !== nums[i]){ const temp = nums[nums[i] - 1] nums[nums[i] - 1] = nums[i] nums[i] = temp } } for(let i = 0; i < len; i++){ if(nums[i] !== i + 1){ return i + 1 } } return len + 1};

4. 提交结果

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。