今天和大家聊的问题叫做 缺失的第一个正数，我们先来看题面：
https://leetcode-cn.com/problems/first-missing-positive/
Given an unsorted integer array, find the smallest missing positive integer.
题意
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数 。你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
样例
示例 1: 输入: [1,2,0] 输出: 3 示例 2: 输入: [3,4,-1,1] 输出: 2 示例 3: 输入: [7,8,9,11,12] 输出: 1
题解
由于线性时间和常数空间的要求，我们开不了数组，用不了哈希表，不能排序。能用的就只有数组本身以及额外常数个变量。。。
我们考虑如果整数都出现，那么最后数组排列应该是[1,2,3,4,5,…,n]，每个都是递增1。于是乎，如果我们最后也排列成这种形式，那么只要不满足nums[i]-nums[i-1]不等于1，那么就找到了最小的未出现的整数，但是我们没法排序。
所以我们可以强行另数组下标和存的值产生联系-> 令数字i出现在下标为i-1的位置，如果会越界则不做处理。比如[3,4,-1,1]->[-1,4,3,1]->[-1,1,3,4]->[1,-1,3,4];
class Solution { public int firstMissingPositive(int[] nums) { for(int i=0;i<nums.length;){ if(nums[i]>0&&nums[i]<=nums.length&&nums[i]!=nums[nums[i]-1]){ //确定nums[i]的值对应的下标不越界，同时排除num[i]本身位置正确或者nums[i]应该放入的位置nums[i]-1原本就是nums[i](如[1,1]) int index = nums[i];// nums[i] = nums[index -1]; nums[index -1]=index; //换位置之后需要继续判断换过来的值是否在对的位置上，因此不能i++; }else{ i++; } } for(int i=0;i<nums.length;i++){ if(nums[i]!=i+1){ return i+1; } } return nums.length+1; } }
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。
