leetcode第41题 缺失的第一个正数

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

困难题，不会做。

class Solution { public int firstMissingPositive(int[] nums) { int n = nums.length ; for(int i = 0 ; i < n ; i ++){ if(nums[i]<=0){ nums[i] = n + 1 ; } } for(int i = 0 ; i < n ; i ++){ int num = Math.abs(nums[i]); if(num <= n ){ nums[num-1] = - Math.abs(nums[num-1]); } } for(int i = 0 ; i < n ; i ++){ if(nums[i]>0){ return i + 1 ; } } return n + 1 ; } }

第一种方法思路： 1，先把所有不再【1，n】区间的数，设置为n+1 2，遍历数组，把绝对值小于n的数，所对应的位置上的数变成负数（无论是多少，变成负的，即可） 3，找到第一个不是负数的位置，然后加1. 评价，非常巧妙。相当于为每个1，n范围内的数进行了负数的标记。

第二种方法：

class Solution { public int firstMissingPositive(int[] nums) { int n = nums.length ; for(int i = 0 ; i < n ; i ++){ while(nums[i]>0 && nums[i] <= n && nums[nums[i]-1] != nums[i]){ int temp = nums[i] ; nums[i] = nums[nums[i]-1] ; nums[temp-1] = temp ; // 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 ; } }

思路：把每个【1，n】之间的数放到他应该在的地方（3就放在2号位） 1，把每个在【1，n】之间的数，放在其对应的位置上。 2，找到第一个nums[i] != i +1 的数。就是那个最小值。

两种方法，都是应用的自身数组，一个进行标记，一个进行置换。

关键的点没有想到。就是长度为n的数组，最大的结果也就是n+1不可能更大了。 否则就应该在【1，n】之间。