缺失的第一个正数

问题描述

leetcode41 寻找数组中缺失的第一个正数。
第一个指的是按照数字顺序，在数组中没有出现的正整数

要求

时间复杂度O(n)
空间复杂度O(1)

解决思路

基本解法：这个超出了时间复杂度的要求
1. 先找出数组中最小的正整数，如果最小正值为 1，则找比 1 大的在数组中没出现过的那个数，返回。
2. 否则，直接返回 1。
高级解法：第一次遍历，更改数组元素的存储结构，使之成为这样的结构：

　　　　　　　　[1, 一些大于1的正数区，负数区，一些比本身下标大的正数值区]。

　　　　　　　　第二次遍历找出符合条件的最小正值。

原作为什么会想到这样的解法来做这个题呢？为什么要把数组变成这样的形式？

这道题的关键就是对数组中存在 1 这种情况进行处理。如果有1，则需要找到比 1 大的最小正值。

利用好数组索引与数组元素值的关系，对于那些元素值大于索引值的部分不需要进行更改。只需要把那些大于0，且值与索引不等的情况才需要交换更改。

代码呈现

普通解法。

 1    public static int firstMissingPositive(int[] nums) {
 2         if (nums.length==0) { return 1; }
 3         int res = Integer.MAX_VALUE;
 4         // 找到该数组中最小的正数
 5         for(int i=0; i<nums.length; i++) {
 6             if (nums[i]>0) {
 7                 res = res < nums[i] ? res : nums[i];
 8             }
 9         }
10 
11         if (res == 1) {
12             // 当数组中出现最小正数 1 的时候，是最难处理的时候。需要去找比1大的在数组中没出现过的那个数
13             // 时间复杂度O(n2)，因为在while循环里还有for循环。所以这种方式是不完全正确的。
14             boolean findFlag = true;
15             while (findFlag) {
16                 findFlag = false;
17                 for(int j=0; j<nums.length; j++) {
18                     if (nums[j] == res+1) {
19                         res += 1;
20                         // System.out.println("循环内："+res);
21                         findFlag = true;
22                         break;
23                     }
24                 }
25             }
26             // System.out.println(res+1);
27             return res+1;
28         }
29         // 全负或者最小正数大于1时，取1
30         return 1;
31     }

更改数组的形式

 1     public static int firstMissingPositive3(int[] A) {
 2         int n = A.length;
 3         if (n == 0) return 1;
 4         for (int i = 0; i < n; ) {
 5             if (A[i] > 0 && A[i] <= n && A[i]-1 != i){
 6                 int a = A[i];
 7                 A[i] = A[a - 1];
 8                 A[a - 1] = a;
 9             }
10             else ++i;
11         }
12 
13         for(int j:A) {
14             // System.out.println(j);
15         }
16 
17         for (int i = 0; i < n; ++i){
18             if (A[i] != i + 1)
19                 return i + 1;
20         }
21         return n+1;
22     }

原作这样写，让我有种错觉：那就是这道题的代码不是为了题目存在的，而是这道题是为了这段代码存在的。其中更改数组结构的代码

1    for (int i = 0; i < n; ) {
2             if (A[i] > 0 && A[i] <= n && A[i]-1 != i){
3                 int a = A[i];
4                 A[i] = A[a - 1];
5                 A[a - 1] = a;
6             }
7             else ++i;
8         }

和下面的代码一致：

1  for (int i = 0; i < n; i++) {
2             while (nums[i] >= 1 && nums[i] <= n && nums[i] - 1 != i) {
3                 //swap(nums, nums[i] - 1, i);
4                 int temp = nums[i];
5                 nums[i] = nums[temp-1];
6                 nums[temp-1] = temp;
7             }
8         }

仍然是在 for 里面包含了 while 循环，看起来像是 n^2 复杂度，但由于其三个条件的约束，导致内层循环达到O(1)复杂。这点算是可以学习的地方。

缺失的第一个正数

问题描述

要求