LeetCode-困难进阶-41-缺失的第一个正数-原地解决(C)

这题是我解决的第一道困难的LeetCode,值得纪念。
而且还完成了进阶要求!

题目

给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。

进阶:你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗?

示例 1:

输入:nums = [1,2,0]
输出:3
示例 2:

输入:nums = [3,4,-1,1]
输出:2
示例 3:

输入:nums = [7,8,9,11,12]
输出:1
 

提示:

0 <= nums.length <= 300
-231 <= nums[i] <= 231 – 1

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/first-missing-positive
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

  • 这题能满足进阶要求,但只是因为这题的nums[]数组大小有限,如果nums[]大小不限,这题无法满足常数项的额外空间。
  • 这题是找最小未出现的正整数,那么如果nums[]的大小为numsSize,则最小未出现的正整数,一定在1~numsSize+1之间。
  • 为了记录所有出现过的数,设置一个numsSize[]大小的hasAppeared[]数组,用来记录nums[]出现的数,且由于最小未出现正整数<=numsSize+1,hasAppeared[]只需要numsSize大小即可。
    • hasAppeared[n]里的值,表示n+1是否出现过,用1表示出现过,非1表示未出现过。
      • C语言中,未初始化的数组可能是随机值,也可能是0,这题在LeetCode的编译器里直接用1表示不会出现问题。
  • 那么在代码里面只需要这么做即可:
    • 设置一个numsSize大小的hasAppeared[]数组。
    • 遍历nums[],如果nums[pos]的值是<=numsSize的正整数,那么就将hasAppeared[ nums[pos]-1 ]的值置为1。
    • 遍历完nums[]后,再遍历hasAppeared[],第一个非1的位置即是所求的未出现的最小正整数,如果全1,则是第numsSize+1为未出现的最小正整数。
  • 例如:
    • 对于nums[] = {1, 0, 2};hasAppeared[]的情况为{1, 1, ?}。第一个非1位hasAppeared[2],因此return 2+1,即pos+1
    • 对于nums[] = {1, 2, 3};hasAppeared[]的情况为{1, 1, 1}。全1,因此return 3+1,即numsSize+1。
      • 注:全1时的遍历结束后,pos == numsSize,因此两种情况均可return pos+1。
  • 进阶:你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗?
    • 代码时间复杂度为O(n)+O(n),即O(n)。
    • 使用了n的不定空间。
      • 对于本题来说,numsSize不超过300,因此可以将长度为n的不定空间改成长度为300的空间,就可以满足进阶要求了。
    • 如果要实现原地解决的话,我的想法在现在的基础上改进:
      • 依然是遍历nums[],如果0<nums[pos]<=numsSize,就交换nums[pos]和nums[ nums[pos]-1 ],再将nums[pos]置1。
      • 然后对nums[]执行如上hasAppeared的操作。
    • 是的,我想完想法发现好简单然后顺便实现了!
    • 现在是只需要两个int就能解决了!
    • 改进完发现原来的还缺点东西,新的思路是这样的:
      • 遍历nums[],如果nums[pos] != pos+1,那么交换nums[pos]与nums[ nums[pos]-1 ],并将pos–。
      • 结束后,遍历一遍nums[],如果全符合nums[pos] == pos+1,就返回numsSize,否则返回pos+1。

代码-普通

/*
设置一个hasAppeared的int数组,大小为numsSize。
如果出现了这个数,就将hasAppeared置1,将nums[]遍历,
结束后,将hasAppeared遍历,如果全为1就表明1~numsSize全出现了,返回numsSize+1
否则返回第一个非1的。
*/

int firstMissingPositive(int* nums, int numsSize){
    int *hasAppeared = (int*)malloc(sizeof(int)*numsSize);
    int pos;
    for(pos=0;  pos<numsSize;   pos++){
        if(nums[pos]<=numsSize && nums[pos]>0) hasAppeared[ nums[pos]-1 ] = 1;
    }
    for(pos=0;  pos<numsSize;   pos++){
        if(hasAppeared[pos] != 1) return pos+1;
    }
    return pos+1;
}

代码-进阶

/*
遍历nums[],如果nums[pos] != pos+1,那么交换nums[pos]与nums[ nums[pos]-1 ],并将pos--。
结束后,遍历一遍nums[],如果全符合nums[pos] == pos+1,就返回numsSize,否则返回pos+1。
*/

int firstMissingPositive(int* nums, int numsSize){
    int pos, temp;
    for(pos=0;  pos<numsSize;   pos++){
        if(nums[pos]<=numsSize && nums[pos]>0 && nums[pos]!=pos+1) {
            temp = nums[pos];
            nums[pos] = nums[ temp-1 ];
            nums[ temp-1 ] = temp;
            if(nums[pos] == nums[temp-1]) nums[pos]=-1;
            pos--;
        }
    }
    for(pos=0;  pos<numsSize;   pos++){
        if(nums[pos] != pos+1) return pos+1;
    }
    return pos+1;
}

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注