字节跳动HardTop
41. 缺失的第一个正数
题目： 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0]
输出：3
示例 2：
输入：nums = [3,4,-1,1]
输出：2
示例 3：
输入：nums = [7,8,9,11,12]
输出：1
提示：
- 1 <= nums.length <= 5 * 105
- 231 <= nums[i] <= 231 - 1
顶级解题思路（JOJO的奇妙比喻）：
让每个数字n都回到下标为n-1的家里。
而那些没有回到家里的就成了流浪在外，他们要么是根本就没有自己的家（数字小于等于0或者大于nums.size()），要么是自己的家被别人占领了（出现了重复）。
这些流浪汉被临时安置在下标为i的空房子里，之所以有空房子是因为房子i的主人i+1失踪了（数字i+1缺失）。
Java代码：
class Solution {
public int firstMissingPositive(int[] nums) {
int len = nums.length;
for (int i = 0; i < len; i++) {
while (nums[i] > 0 && nums[i] <= len && nums[i] != nums[nums[i] - 1]) {
swap(nums, nums[i] - 1, i);
}
}
for (int i = 0; i < len; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return len + 1;
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
