欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode--41.缺失的第一个正数(C)

程序员文章站 2022-06-03 11:20:40
...

1. 题目描述

难度:困难
LeetCode--41.缺失的第一个正数(C)

2. 题目分析

这道题本质上是很简单的,但是加上了这个条件就会变得的很难实现:

  • 算法的时间复杂度为O(n), 只能使用常数级别的空间

这句话就说明了我们不能暴力穷举法(O(n^2)),以及对输入数组进行快速排序(nlogn)。具体的实现方法可以是这样的:

我们将大于0并且不大于数组长度的元素放在对应下标的位置上,然后遍历完毕之后,在次检查每个下标是否对应该位置上的元素,如果不是,那么这个元素就是我们要找到的缺失的最小正数,如果每个下标都对应上了,那么缺失的元素就是数组长度加一。

这个方法可以用两种方式实现,一种是在原数组上就行两个元素的swap,一种是新建一个数组,然后将值映射在相应的位置上。

3. C语言实现

3.1 申请额外空间实现

代码如下:

int firstMissingPositive(int* nums, int numsSize){
    int i;
    // 动态申请数组长度相等的数组temp
    int* temp = (int *)malloc(sizeof(int)*numsSize);
    for(i = 0; i < numsSize; i++){
    	// 如果该元素大于0并且不大于数组长度,将其对应temp位置上的元素置1
        if(nums[i] > 0 && nums[i] <= numsSize){
            temp[nums[i]-1] = 1;
        }
    }
    // 遍历temp,如果该位置上的元素不是1,那么i+1就是我们要输出的结果
    for(i = 0; i < numsSize; i++){
        if(temp[i] != 1){
            return i+1;
        }
    }
    return i+1;
}

运行结果为:
LeetCode--41.缺失的第一个正数(C)

3.2 原数组实现

代码如下:

int firstMissingPositive(int* nums, int numsSize){
    int i, temp;
    // 当元素同时满足条件:1.大于0 2.不大于数组长度 3. 与下标不匹配 4.与匹配位置的元素不相等 时,交换对应位置上的元素
    for(i = 0; i < numsSize; i++){
        while(nums[i] > 0 && nums[i] <= numsSize && nums[i]!= i+1 && nums[i]!=nums[nums[i]-1]){
            temp = nums[i];
            nums[i] = nums[nums[i]-1];
            nums[temp-1] = temp;
        }
    }
    for(i = 0; i < numsSize; i++){
        if(nums[i] != i+1){
            return i+1;
        }
    }
    return i+1;
}

运行结果为:
LeetCode--41.缺失的第一个正数(C)

相关标签: # •Array