题目描述查看：https://leetcode-cn.com/problems/first-missing-positive/
题目的意思是给定一个无序数组，对数组排序后，缺失的最小正整数。要求时间复杂度O(n)，常数级空间复杂度。
时间复杂度是O(n)，那么先排序后查找的思路就行不通了，排序算法在最坏情况下时间复杂度不低于O(nlogn)。
缺失的最小正整数只能是[1,len+1]之间的一个数。
根据这个发现，可以把数组元素的值和数组下标映射起来，index = 0,arr[0] = 1;index = 1,arr[1] = 2;建立数组元素值和索引之间的映射，为每个数找到位置。
由于比len大的数不影响缺失值，所以碰见比len大的数不改变位置。
映射好数组后，查找数组元素，如果数组元素和下标不满足映射关系，这个下标位置就是缺失的数的位置，所以缺失的数是index+1。
1 for (int i = 0; i < nums.length; i++) { 2 if(nums[i] != i+1){ 3 return i+1; 4 } 5 }
1 public int firstMissingPositive(int[] nums) { 2 if (nums.length == 0)return 1; 3 for (int i = 0; i < nums.length; i++) { 4 while(nums[i] != i+1 && nums[i] > 0){ 5 //比len大的数，不影响结果，不找位置。 6 if(nums[i] > nums.length)break; 7 int index = nums[i] - 1; 8 int tmp = nums[index]; 9 //避免要交换的2个数值一样，造成死循环。 10 if(tmp == nums[i]) 11 break; 12 nums[index] = nums[i]; 13 nums[i] = tmp; 14 } 15 } 16 17 for (int i = 0; i < nums.length; i++) { 18 if(nums[i] != i+1){ 19 return i+1; 20 } 21 } 22 return nums.length+1; 23 }
原文：https://www.cnblogs.com/vshen999/p/12606311.html