leetcode41 缺失的第一个正数

川长思鸟来 2021-12-03 23:15 215阅读 0赞

*  问题描述

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

*  要求

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

*  解决思路

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

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

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

> 原作为什么会想到这样的解法来做这个题呢？为什么要把数组变成这样的形式？
> 
> 1.  这道题的关键就是对数组中存在 1 这种情况进行处理。如果有1，则需要找到比 1 大的最小正值。
> 2.  利用好数组索引与数组元素值的关系，对于那些元素值大于索引值的部分不需要进行更改。只需要把那些大于0，且值与索引不等的情况才需要交换更改。

*  代码呈现

1.  普通解法。
    
        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     }
2.  更改数组的形式
    
        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)复杂。这点算是可以学习的地方。

转载于:https://www.cnblogs.com/dogeLife/p/11052364.html