[力扣_41] 寻找第一个缺失的正数

题目入口:点击进入

题目分析:

我们先从给定的样例入手分析,如下所示:

image-20210122071802361

从上图对示例的分析我们不难知道如何找寻第一个正整数,分为以下两种情况:

  • 第一个正整数代表数组中未存在的最小正数,而在一个序列中,理想情况便是递增,也就是说如果在这个序列中出现了小于1或大于n的数,这个数组在[1,n]这个闭区间内一定有数值缺失,若其满足了理想情况,则缺失的第一个正数即为数组长度加一,我们可以得知,缺失的这个正数一定在[1,n+1]这个闭区间内
  • 而又可以得出,若数组中的序列满足理想情况,代表从1开始直到数组长度的所有数全存在于数组中的话,第一个缺失的正数即为n+1
  • 否则缺失的这个数即为从1开始到达最先被不存在于[1,n]的那个数

Hash表

从上分析我们不难得出可用数组模拟Hash表来得出答案,算法思路如下

  1. 建立一个数组长度大小的数组,数组下标对应作健,而数组的元素作值,从上述我们可以知道,理想情况即使序列中的元素是递增存在的,而这正好对应了Hash数组中的下标
  2. 扫描给定的数组,将存在于 [1,n) 的数在 Hash表中标记为1 由于数组下标是为0的,所以在标记时,其下标需要-1
  3. 扫描Hash 表, 返回 第一个为0,也就是被代替的数 的下标(由于数组下标从0开始,所以我们需要返回它的下标+1)

如下图所示:

image-20210122074130834

代码如下所示:

int firstMissingPositive(int* nums, int numsSize){
    
    int *Hash=(int*)malloc(sizeof(int)*numsSize);
    for(int k=0;k<numsSize;k++) Hash[k]=0;//初始化哈希表,初始状态下全为0
    
    for(int i=0;i<numsSize;i++){
        if(nums[i]>=1&&nums[i] <= numsSize){//满足理想情况的数标记为1
            Hash[nums[i]-1]=1;//扫描nums数组构造Hash表
        }
    }

    int j=0;
    while(j<numsSize){//扫描Hash数组,第一个未被标记的数即为缺失的数,返回其下标+1
        if(Hash[j]!=1){
            break;
        }
        j++;
    }
    return j+1;
}
时间复杂度分析

在上述解法中,创建Hash表的时间复杂度为n,构造Hash表的复杂度为n,扫描Hash表的最坏时间复杂度为n,则该算法省略常数的时间复杂度为O(n)

空间复杂度分析

在上述解法中,我们需要创建一个辅助数组作为Hash表,表长度取决于给定的nums数组的长度,即为O(n)

原地Hash表

在第一种解法中虽然达到了时间复杂度的要求,但未达到空间复杂度的要求,从第一个方法可以知道,所用到的Hash表本身也是一个数组,而要达到的效果就是判断其下标是否于其值相等同(值减1),而极端情况下就是所有数值都恰到好处的在它应在的位置,这时返回n+1即可(n为数组长度)

是否可以将原nums数组当作Hash表使用呢(liweiwei大神题解)?算法思路如下所示:

  • 由于题目要求我们「只能使用常数级别的空间」,而要找的数一定在 [1, N + 1] 左闭右闭(这里 N 是数组的长度)这个区间里。因此,我们可以就把原始的数组当做哈希表来使用。事实上,哈希表其实本身也是一个数组;
  • 我们要找的数就在 [1, N + 1] 里,最后 N + 1 这个元素我们不用找。因为在前面的 N 个元素都找不到的情况下,我们才返回 N + 1;
  • 那么,我们可以采取这样的思路:就把 1 这个数放到下标为 0 的位置, 2 这个数放到下标为 1 的位置,按照这种思路整理一遍数组。然后我们再遍历一次数组,第 1 个遇到的它的值不等于下标的那个数,就是我们要找的缺失的第一个正数。
  • 这个思想就相当于我们自己编写哈希函数,这个哈希函数的规则特别简单,那就是数值为 i 的数映射到下标为 i - 1 的位置。

image-20210122080621411

这儿需要考虑,若有重复的怎么办,从上分析我们可以得知,一个萝卜一个坑,每个数字只有正确的位置,而通过一次交换该值并会被交换到正确的位置上,所以我们可以通过比较当前数值当前数值正确位置上的数值是否相等来判断其正确位置上是否已有正确的数值:当nums[i]!=nums[nums[i]-1],这儿nums[i]就是当前位置,而nums[i]-1,就是其应该被调换到正确位置上的下标,而nums[nums[i]-1]就是当前数值正确位置上的数值

整理一下:当nums[i]>0&&nums[i]<=numsSize&&nums[i]!=nums[nums[i]-1]的时候调换位置,从左到右解释为(当前数值大于0,当前数值小于或等于数组长度,当前数值不等于其正确位置上的数值)

而被调换过来后,也许被调换的数一样满足以上条件,所以这儿要使用while循环多次判断当前位置,直到当前位置上的值不满足条件再判断下一个值。

代码如下所示:

int firstMissingPositive(int* nums, int numsSize){
    for(int i=0;i<numsSize;i++){
        //两个交换的数相等时,防止死循环
        while(nums[i]>0&&nums[i]<=numsSize&&nums[i]!=nums[nums[i]-1]){
          //交换
            int temp=nums[i];
            nums[i]=nums[nums[i]-1];  
            nums[temp-1]=temp;
        }
    }
    //寻找缺失的数
    for(int k=0;k<numsSize;k++)
        if(nums[k]-1!=k) return k+1;
    return numsSize+1;
}

本文链接:

https://nullcode.fun/126.html
1 + 3 =
快来做第一个评论的人吧~