第三方网站建设/上海网站外包

题目重述

给你一个未排序的整数数组 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 * 105
-231 <= nums[i] <= 231 - 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/first-missing-positive
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

• 缺失的第一个正数一定在[1,N+1]范围内，因为最极端的情况就是长度为N的数组，放了1,2,3,4......N这样的元素，此时返回N+1,即缺失的第一个正数
• 把题目给的元素“归位”，即元素1放到0位置，2放到1位置，这样类推，放好之后，从头判断一下，对应下标有没有放对应值，如果没有返回下标+1就是其缺失的第一个正数

Java实现

class Solution {public int firstMissingPositive(int[] nums) {for(int i=0;i<nums.length;i++){while(nums[i]>0 && nums[i]<=nums.length && nums[nums[i]-1]!=nums[i]){int t = nums[nums[i]-1];nums[nums[i]-1] = nums[i];nums[i] = t;}}// 此时 应该为，[-1,1,3,4]for(int i=0;i<nums.length;i++){if(nums[i]!=i+1){return i+1;}}return nums.length+1;}
}