蓝桥杯day5 _缺失的第一个正数-哈希或搜索

标题:缺失的第一个正数

给你一个未排序的整数数组 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

普通版

#include <iostream>
#include<algorithm>∥数组排序
#include<string>
using namespace std;

int findNumber(int a[])
{
    int i=0,j=1;
    sort(a,a+7);
    while(true){
        if(i == a.length)
        {
             return j; ∥返回n+1
        }

        if(a[i]<=0)
        {
            i++;
            continue;
        }
        if(i>0 && a[i] == a[i-1]
        {
            i++;
            continue;
        }
        if(a[i]==j)
        {
            i++;
            j++;
            continue;
        }
        return j; ∥返回最小值

    }
}

int main()
{
    int a[]={-1,-5,0,1,2,4,5};
    cout<<findNumber(a);
    return 0;
}

进阶:哈希

蓝桥杯day5 _缺失的第一个正数-哈希或搜索

1:将数组中所有负数变为正数(大于N的正数)
2:将数组中小于N的数找出
3: 以2中找到的数为下标(减去1)
4:将下标- 1对应的数组值修改为负数
5:找到第一个正数,返回其下标

代码

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int& num: nums) {
            if (num <= 0) {
                num = n + 1;
            }
        }
        for (int i = 0; i < n; ++i) {
            int num = abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -abs(nums[num - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
};
上一篇:计算机组成原理概念学习DAY5——*处理机


下一篇:jsp 不显示换行 Eclipse复制一行快捷键