LeetCode代码分析——|LeetCode代码分析—— 41. First Missing Positive（桶排序思想） LeetCode代码分析——41.FirstMis

题目描述 Given an unsorted integer array, find the smallest missing positive integer.
给定一个未排序的整数数组，找出其中缺少的最小的正整数。
Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Note:
Your algorithm should run in O(n) time and uses constant extra space.
你的算法要求时间复杂度O(n)并且空间复杂度为常量。
思路分析 【LeetCode代码分析——|LeetCode代码分析—— 41. First Missing Positive（桶排序思想）】时间复杂度O(n)，排序是肯定不行了。空间复杂度要求常量，所以只能把额外的空间用作交换。结合题目要求，需要找缺少的最小的整数，假如有10个数，那么这个缺少的最小整数必然在1-11之间。（11表示10个数是1-10连续的，反证法可得，如果缺少的最小整数大于11，那么说明前面11个必然是连续的，而数组最多只有10个数，矛盾）
因此，由于时间复杂度要求O(n)可以想到根据桶排序的思想，由于题目要求所以排序结果必然可以放在原数组中，因为本题的目的不在于排序，所以可以在桶排序的思想上进行变种，直接利用原数组，空间复杂度O(1)。

LeetCode代码分析——|LeetCode代码分析—— 41. First Missing Positive（桶排序思想）

文章图片
桶排序思想原地交换
使用交换，让每个数组下标对应数字，例如例二的[3,4,-1,1]，可以用数组下标0对应数字1，数组下标1对应数字2...则交换后的数组应该为[1,-1,3,4]。然后再遍历一次排序好的数组，找到第一个下标和内容不符的数字，就是结果。
想明白以上过程剩下的实现问题就很简单了，遍历数组，如果当前桶位置的数字与下标不符，例如nums[0]与数字3不符，则交换nums[0]与nums[3 - 1]，当然在交换前要判断3是否超过数组上下界。例外，需要注意[2,2]的情况，既有数字重复，这种情况下目标位置其实已经匹配好了，如果再交换将会无限循环下去，所以要判断下nums[cur]与nums[i]是否相等。
代码实现

public class Solution {/** * 157 / 157 test cases passed. *Status: Accepted *Runtime: 14 ms * * @param nums * @return */ public int firstMissingPositive(int[] nums) { for (int i = 0; i < nums.length; i++) { if (nums[i] != i + 1) { // swap nums[i] with nums[nums[i] - 1] int cur = nums[i] - 1; if (cur >= 0 && cur < nums.length && nums[cur] != nums[i]) { int temp = nums[i]; nums[i] = nums[cur]; nums[cur] = temp; // 交换完以后的数字有可能还要再交换，所以i--，该位置再判断一次 i--; } } }for (int i = 0; i < nums.length; i++) { if (nums[i] != i + 1) { return i + 1; } } return nums.length + 1; } }