力扣 41.缺少的第一个正整数

题目描述：

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

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

示例 1：

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

示例 2：

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

提示：

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1

题解：

考虑将每一个元素x放在对应位置的下标处，比如，元素值x等于3，就放在下标为2的位置，因此数组3，2，1在重新放置之后们就会成为：1，2，3，即元素x放在下标为x-1的位置。

遍历一遍数组，如果发现现在i位置的元素值x不等于i+1，说明现在需要进行元素交换，让元素x放在它本来应该放置的位置x-1处，可以使用自定义的交换函数change(nums，i，x-1)，即让i位置元素和x-1位置元素进行交换。

但是注意，交换之前，我们需要确定，现在i位置元素是否是正整数，如果不是的话，对于一个负数或0来说，在我们最终的数组中实际是没有该元素的位置的，因此交换操作不需要对负数和0进行操作，如果遍历到负数或0直接跳过；

其次，如果现在数组大小是4，即下标范围值[0,3]，但是某一个数组元素值为7，该元素需要放置在下标为6的位置，但是数组放不下，因此这种情况也不需要进行交换排序，直接跳过。

综上所述，最终需要进行排序的前提条件是：

1、当前元素大小小于等于数组大小

2、当前元素值>=1

3、当前元素没有放在它实际应该放置的位置，即nums[i]!=nums[nums[i]-1]

在一次交换之后，当前位置上是否就是应该放置的值，这也是不确定的，因此上面我们实现的是将i位置的值放在正确的位置上，但是交换之后的值是否在正确的位置上还是不确定的，因此还需要继续交换，所以这里判断是否需要交换的条件要使用while循环而不是if循环。

使用while循环进行是否可以进行交换的判断的时候，如果出现重复元素在原数组中出现，那么也可以正常进行判断交换，因为，一旦其中一个元素交换到正确的位置上，那么下一个元素进行while判断的时候，nums[i]!=nums[nums[i]-1的条件就不满足，自然不会造成死循环，同时这里使用的是判断当前位置的值是否放在正确位置，而不是当前位置是否放置正确元素，因为现在遍历到当前位置，能确定的就是当前位置的值，以及当前位置的元素应该放到哪里，但是不能确定当前位置应该放置的元素现在在数组的什么位置，因此该判断条件要这么写。

代码实现：

 public static int firstMissingPositive(int[] nums) {//原地排序数组，将值为x的元素放在下标x-1的位置for (int i = 0; i < nums.length; i++) {while(nums[i]>=1&&nums[i]<=nums.length&&nums[i]!=nums[nums[i]-1]){check(nums,i,nums[i]-1);}}for (int j = 0; j < nums.length; j++) {if(nums[j]!=j+1){return j+1;}}return nums.length+1;}public static void check(int[] a,int i ,int j){int temp = a[i];a[i] = a[j];a[j] = temp;}

知识点：

对于这种数组交换来实现每一个元素都在自己应该在的位置的想法一开始觉得不能实现，因为觉得交换之后现在位置上的元素可能还是不满足要求，再进行交换，会不会将之前排好序的位置打乱，实际上，这样的担忧是不必要的，因为每个元素只有一个确定的位置，要么能够交换就交换的放置，要么因为在当前数组放不下该元素或者该元素小于1就不交换，总之，只要在while判断条件下进行的交换总能将新交换到当前位置的元素再交换到正确的位置，直到新交换到当前位置的元素已经不满足要交换的条件了，继续遍历下一个元素进行新一轮的交换即可。