原题地址：缺失的第一个正数
给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
说明:
你的算法的时间复杂度应为$O(n)$，并且只能使用常数级别的空间。
桶排序
桶排序 (Bucket sort) 或所谓的 箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（$O(n)$）。但桶排序并不是 比较排序，他不受到 $O(nlogn)$ 下限的影响。
本题要求找到没有出现的最小的正整数，只要我们能将数组排序，然后扫描一次就能马上得到答案。但是题目要求时间复杂度为$O(n)$，而正常排序的时间复杂度下限为$O(nlogn)$，显然是不符合要求的。
所以我们可以利用题目中数组的特殊性，将每个数字n放到第n个位置上，这只需要一次遍历就可以达到，然后扫描一次就可以找出哪个数字是未出来的，这就是桶排序的思想。
具体的实现代码如下：
/**
* @param {number[]} nums
* @return {number}
*/
const firstMissingPositive1 = function(nums) {
// 桶排序
for (let i = 0; i < nums.length;) {
let temp = nums[i];
// 对于1-n范围内且没在它应有的位置上的都通过交换放到它应待的位置上去
// 超过范围的不用处理
// 如果要交换的数和当前的数相等也不用处理，否则会陷入死循环
// 虽然这里还有一次循环，但由于只用处理未归位的数字，每个数字只会被处理一次，所以实际复杂度还是线性的
if (temp < nums.length && temp > 0 && temp - 1 !== i && nums[temp - 1] !== temp) {
nums[i] = nums[temp - 1];
nums[temp - 1] = temp;
} else {
i++; // 处理下一个数
}
}
// 扫描找出第一个未出现的数字n
for (let i = 0; i < nums.length; i++) {
if (nums[i] !== i + 1) {
return i + 1;
}
}
// 如果全部都出现了，则第一个未出现的为n+1
return nums.length + 1;
};
测试：
let start = new Date();
const test = firstMissingPositive1;
console.log(test([1, 2, 0])); // 3
console.log(test([3, 4, -1, 1])); // 2
console.log(test([7, 8, 9, 11, 12])); // 1
console.log(test([])); // 1
console.log(test([1, 1])); // 2
console.log(new Date().getTime() - start.getTime()); // 8
时间复杂度： 时间复杂度为$O(n)$
空间复杂度： 原地处理，空间复杂度为$O(1)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 8,2019