LeetCode 第 41 题：“缺失的第一个正数”题解
题解地址：桶排序 + 基于“异或运算”交换两个变量的值（Python 代码、Java 代码）。
说明：文本首发在力扣的题解版块，更新也会在第 1 时间在上面的网站中更新，这篇文章只是上面的文章的一个快照，您可以点击上面的链接看到其他网友对本文的评论。
传送门：41. 缺失的第一个正数。
给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0] 输出: 3 示例 2:
输入: [3,4,-1,1] 输出: 2 示例 3:
输入: [7,8,9,11,12] 输出: 1 说明:
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。
桶排序 + 基于“异或运算”交换两个变量的值（Python 代码、Java 代码）
这道题使用桶排序的思路，即 “一个萝卜一个坑”。在学习“排序算法”的时候，可能会忽略“桶排序”的作用，但它的思想的确可以解决一些特定问题。
“桶排序”的思想，有些地方也把它叫做“抽屉原理”，以下介绍来自[“百度百科”之“抽屉原理”词条]：
抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有 n + 1 个元素放到 n 个集合中去，其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。
思路分析：可以就使用题目中的例子，在纸上写写画画，就能得出思路，只不过在编码上需要注意一些细节。
下面是“桶排序”过程。
（温馨提示：下面的幻灯片中，有几页上有较多的文字，可能需要您停留一下，可以点击右下角的后退 “|◀” 或者前进 “▶|” 按钮控制幻灯片的播放。）
如图所示：我们可以把数组进行一次“排序”，“排序”的规则是：如果这个数字 i 落在“区间范围里”，i 就应该放在索引为 i - 1 的位置上，下面具体解释。
1、数字 i 落在“区间范围里”；
例如：[3, 4, -1, 1]，一共 4 个数字，那么如果这个数组中出现 “1”、“2”、“3”、“4”，就是我们重点要关注的数字了；
又例如：[7, 8, 9, 11, 12] 一共 5 个数字，每一个都不是 “1”、“2”、“3”、“4”、“5” 中的一个，因此我们无须关注它们；
2、i 就应该放在索引为i - 1 的位置上；
这句话也可以这么说 “索引为 i 的位置上应该存放的数字是 i + 1”。
就看上面那张图，数字 应该放在索引为 的位置上，数字 应该放在索引为 的位置上，数字 应该放在索引为 的位置上。一个数字放在它应该放的位置上，我们就认为这个位置是“和谐”的，看起来“顺眼”的。
按照以上规则排好序以后，缺失的第 个正数一下子就看出来了，那么“最不和谐”的数字的索引 ，就为所求。那如果所有的数字都不“和谐”，数组的长度 就为所求。
参考代码 1：
Python 代码：
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
size = len(nums)
if size == 0:
return 1
for i in range(size):
while nums[i] > 0 and nums[i] <= size:
if nums[nums[i] - 1] == nums[i]:
# 如果已经在合适的位置上，就不用交换了
break
# 这里我单独把交换数组两个位置的方法封装起来，是为了不让自己出错，这一行代码有点绕
# 就要把它放到合适的位置上，i 应该放在索引为 i - 1 的位置上
self.__swap(nums, i , nums[i] - 1)
# 从头到尾看一遍
for i in range(size):
if nums[i] != i + 1:
return i + 1
return size + 1
def __swap(self, nums, index1, index2):
if index1 == index2:
return
nums[index1], nums[index2] = nums[index2], nums[index1]
Java 代码：
import java.util.Arrays;
public class Solution {
// 关键字：桶排序，什么数字就要放在对应的索引上，其它空着就空着
// 最好的例子：[3,4,-1,1]
// 整理好应该是这样：[1,-1,3,4]，
// 这里 1，3，4 都在正确的位置上，
// -1 不在正确的位置上，索引是 1 ，所以返回 2
// [4,3,2,1] 要变成 [1,2,3,4]，*** Offer 上有类似的问题。
// 这里负数和大于数组长度的数都是"捣乱项"。
public int firstMissingPositive(int[] nums) {
int len = nums.length;
for (int i = 0; i < len; i++) {
// 前两个是在判断是否成为索引
// 后一个是在判断，例如 3 在不在索引 2 上
// 即 nums[i] ?= nums[nums[i]-1] 这里要特别小心
while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
// 第 3 个条件不成立的索引的部分是 i 和 nums[i]-1
swap(nums, nums[i] - 1, i);
}
}
// 调试代码
// System.out.println(Arrays.toString(nums));
for (int i = 0; i < len; i++) {
// [1,-2,3,4]
// 除了 -2 其它都满足： i+1 = num[i]
if (nums[i] - 1 != i) {
return i + 1;
}
}
return len + 1;
}
private void swap(int[] nums, int index1, int index2) {
if (index1 == index2) {
return;
}
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
public static void main(String[] args) {
Solution solution = new Solution();
// int[] nums = {3, 4, -1, 5};
int[] nums = {4, 3, 2, 1};
int firstMissingPositive = solution.firstMissingPositive(nums);
System.out.println(firstMissingPositive);
}
}
复杂度分析：
- 时间复杂度：，这里 是数组的长度，其实只要看这个数组一遍，就可以知道每个数字应该放在哪个位置，所以时间复杂度是 。
- 空间复杂度：，桶排序在原地进行，没有使用额外的存储空间。
补充内容：
交换两个整数，有两种比较 tricky 的做法。下面只给出结论，不给出解释（我也解释不了）。
交换两个变量的值，例如 a 和 b，不使用第三个变量，有两种不同的方法：
| 基于异或运算 | 基于加减法 |
|---|---|
a = a ^ bb = a ^ ba = a ^ b | a = a + bb = a - ba = a - b |
我理解的方式就是自己在纸上写几个例子，并且记住这个结论。个人觉得“基于异或运算”交换两个变量的值好记一些，因为右边都一样，左边是 a、b、a。
参考代码 2：基于异或运算交换两个变量的值。
Python 代码：
from typing import List
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
size = len(nums)
# 题目中给出的例子，就是最好的例子
# [3,4,-1,1]
# [-1,4,3,1]
# [-1,1,3,4]
# 3 应该放在索引为 2 的地方
# 4 应该放在索引为 3 的地方
for i in range(size):
# nums[i] > 0 and nums[i] <= size 的意思是：只要是符合索引的数字
# 这里的索引应该认为从 1 开始
# 就要把它放到正确的地方上去，这一步叫 hash
# nums[i] == nums[nums[i]-1]，叫放到了正确的地方
# 例如，3 应该放在索引为 2 的地方，如果不理解，这句话多读几遍
# 所以，先判断这个数字是不是索引
# 然后判断这个数字是不是放在了正确的地方
while 1 <= nums[i] <= size and nums[i] != nums[nums[i] - 1]:
# 交换
self.__swap(nums, i, nums[i] - 1)
# print(nums)
# 再遍历一次，没有放对的就是你要找的
for i in range(size):
# value： [1,2,3,4]
# index： [0,1,2,3]
if i + 1 != nums[i]:
return i + 1
return size + 1
def __swap(self, nums, index1, index2):
# nums[index1], nums[index2] = nums[index2], nums[index1]
nums[index1] = nums[index1] ^ nums[index2]
nums[index2] = nums[index1] ^ nums[index2]
nums[index1] = nums[index1] ^ nums[index2]
Java 代码：
public class Solution {
// 关键字：桶排序，什么数字就要放在对应的索引上，其它空着就空着
// 最好的例子：[3,4,-1,1]
// 整理好应该是这样：[1,-1,3,4]，
// 这里 1，3，4 都在正确的位置上，
// -1 不在正确的位置上，索引是 1 ，所以返回 2
// [4,3,2,1] 要变成 [1,2,3,4]，*** Offer 上有类似的问题。
// 这里负数和大于数组长度的数都是"捣乱项"。
public int firstMissingPositive(int[] nums) {
int len = nums.length;
for (int i = 0; i < len; i++) {
// 前两个是在判断是否成为索引
// 后一个是在判断，例如 3 在不在索引 2 上
// 即 nums[i] ?= nums[nums[i]-1] 这里要特别小心
while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
// 第 3 个条件不成立的索引的部分是 i 和 nums[i]-1
swap(nums, nums[i] - 1, i);
}
}
// 调试代码
// System.out.println(Arrays.toString(nums));
for (int i = 0; i < len; i++) {
// [1,-2,3,4]
// 除了 -2 其它都满足： i+1 = num[i]
if (nums[i] - 1 != i) {
return i + 1;
}
}
return len + 1;
}
private void swap(int[] nums, int index1, int index2) {
nums[index1] = nums[index1] ^ nums[index2];
nums[index2] = nums[index1] ^ nums[index2];
nums[index1] = nums[index1] ^ nums[index2];
}
public static void main(String[] args) {
Solution2 solution = new Solution2();
// int[] nums = {3, 4, -1, 5};
int[] nums = {4, 3, 2, 1};
int firstMissingPositive = solution.firstMissingPositive(nums);
System.out.println(firstMissingPositive);
}
}