面试算法-49-缺失的第一个正数

题目

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

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

解

class Solution {public int firstMissingPositive(int[] nums) {int n = nums.length;for(int i = 0;i < n;i++){// 把数字置换到对应的位置上，在遍历一遍就知道缺失那个了while(nums[i] <= n && nums[i] >0 && nums[nums[i] -1] != nums[i]){int temp = nums[nums[i] -1];nums[nums[i] -1] = nums[i];nums[i] = temp;}}for(int i =0;i< n;i++){if(nums[i] != i +1){return i+1;}}return n+1;}
}