380，缺失的第一个正数（中）
You have to decide whether to trust your own eyes and ears, or what other people say.
你需要决定是相信自己的眼睛和耳朵，还是相信别人的话。
问题描述
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
问题分析
01暴力求解这道题最容易想到的就是暴力求解，我们从1到数组的长度一个个找，如果找到了就继续寻找下一个，如果没找到就直接返回，代码很简单，我们来看下
1public int firstMissingPositive(int[] nums) {
2 for (int i = 1; i <= nums.length; i++) {
3 boolean has = false;
4 for (int j = 0; j < nums.length; j++) {
5 if (nums[j] == i) {
6 has = true;
7 break;
8 }
9 }
10 if (!has) {
11 //没有找到这个数，直接返回
12 return i;
13 }
14 }
15 return nums.length + 1;
16}在算法中我们只要听到暴力二字，就知道这种答案效率肯定不会很高，一般这种答案在面试中非常不占优势
1public int firstMissingPositive(int[] nums) {
2 int len = nums.length;
3 Arrays.sort(nums);//先排序
4 for (int i = 1; i <= len; i++) {
5 int res = binarySearch(nums, i);
6 //一个个查找，如果没找到就返回
7 if (res == -1)
8 return i;
9 }
10 return len + 1;
11}
12
13//二分法查找
14private int binarySearch(int[] nums, int target) {
15 int left = 0;
16 int right = nums.length - 1;
17 while (left <= right) {
18 int mid = left + ((right - left) >> 1);
19 if (nums[mid] == target) {
20 return mid;
21 } else if (nums[mid] < target) {
22 left = mid + 1;
23 } else {
24 right = mid - 1;
25 }
26 }
27 return -1;
28}这种我们可以对数组排序之后再一个个查找，因为排序之后我们可以使用二分法查找，代码也很简单。我们再来看下一种，通过集合来一个个判断
1public int firstMissingPositive(int[] nums) {
2 int len = nums.length;
3 Set<Integer> hashSet = new HashSet<>();
4 for (int num : nums) {
5 hashSet.add(num);
6 }
7 for (int i = 1; i <= len; i++) {
8 if (!hashSet.contains(i))
9 return i;
10 }
11 return len + 1;
12}我们可以把数组中的元素全部放到集合set中，然后在第7到10行，从1到数组长度一个个判断集合set中是否包含这个值，如果没有直接返回。这个也很好理解，下面我们再来看第四种解法
我们还可以把数组中的数字放到对应下标的位置，然后再循环一遍，查看每个位置和对应的下标是否一致，如果不一致直接返回即可，我们就以[3，4，-1，1，7]为例来画个图分析一下
1public int firstMissingPositive(int[] nums) {
2 for (int i = 0; i < nums.length; i++) {
3 //如果在指定的位置就不需要修改
4 if (i + 1 == nums[i])
5 continue;
6 int x = nums[i];
7 if (x >= 1 && x <= nums.length && x != nums[x - 1]) {
8 swap(nums, i, x - 1);
9 i--;//抵消上面的i++，如果交换之后就不++；
10 }
11 }
12 //最后在执行一遍循环，查看对应位置的元素是否正确，如果不正确直接返回
13 for (int i = 0; i < nums.length; i++) {
14 if (i + 1 != nums[i])
15 return i + 1;
16 }
17 return nums.length + 1;
18}
19
20//交换两个数的值
21public void swap(int[] A, int i, int j) {
22 if (i != j) {
23 A[i] ^= A[j];
24 A[j] ^= A[i];
25 A[i] ^= A[j];
26 }
27}
位运算的实现原理和上面第4种答案类似，只不过这里使用的是位运算的方式来解决的。我们知道在java中一个int类型占4个字节是32位，我们可以申请一个数组，1到32我们可以存放到数组的第一个元素中，33到64可以存放到第2个元素中……，有的同学可能好奇，一个数字怎么可能存放32个数呢。因为一个int类型数字是32位的，也就是由32个0和1组成，我们只要统计1在存储中的位置即可，我们来看下代码。
1public int firstMissingPositive(int[] nums) {
2 int length = nums.length;
3 int bit[] = new int[(length - 1) / 32 + 1];
4 for (int i = 0; i < nums.length; i++) {
5 int digit = nums[i];
6 //数组必须在1到length之间才有效
7 if (digit >= 1 && digit <= length) {
8 int index = (digit - 1) / 32;
9 bit[index] = bit[index] | (1 << ((digit - 1) % 32));
10 }
11 }
12 //最后在执行一遍循环，查看对应位置的元素是否正确，如果不正确直接返回
13 for (int i = 0; i < nums.length; i++) {
14 if ((bit[i / 32] & (1 << (i % 32))) == 0)
15 return i + 1;
16 }
17 return length + 1;
18}
06填补替换
下面再来看最后一种解法，也是比较经典的，如果某个元素的值是无效的，他会让数组后面的元素填补过来，然后再判断。注释写在代码中了，有兴趣的也可以看下。
1public int firstMissingPositive(int[] nums) {
2 int start = 0;
3 int end = nums.length - 1;
4 while (start <= end) {
5 int index = nums[start] - 1;
6 if (index == start) {
7 //存放的位置正确
8 start++;
9 } else if (index < 0 || index > end || nums[start] == nums[index]) {
10 //前面两个表示数字不在存放位置范围内，就让数组end位置的元素把这个无效的
11 // 元素覆盖掉，后面一个表示的是index这个位置存放正确了就不需要在存放了
12 nums[start] = nums[end--];
13 } else {
14 //把start对应的元素存放到正确的位置
15 nums[start] = nums[index];
16 nums[index] = index + 1;
17 }
18 }
19 return start + 1;
20}
长按上图，识别图中二维码之后即可关注。
如果喜欢这篇文章就点个"在看"吧