莫比乌斯反演 2021-12-20 11:38 采纳率: 100%
浏览 153
已结题

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

给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

  • 写回答

1条回答 默认 最新

  • 英雄哪里出来 2021年博客之星Top1 2021-12-20 13:23
    关注

    一、分析

    思路如下:
    1)如果在 1 到 maxn 之间的数字,映射到哈希数组中;
    2)然后从 1 开始遍历哈希数组,第一个没有被哈希的就是答案;
    3)所有数字都遍历完毕,仍然没有找到,则答案为 $n+1$。
    

    二、源码

    #define maxn 500001
    int hash[500001], cases = 0;
    int firstMissingPositive(int* nums, int numsSize){
        int i;
        ++cases;
        for(i = 0; i < numsSize; ++i) {
            if(nums[i] > 0 && nums[i] < maxn)
                hash[ nums[i] ] = cases;        // (1) 如果在 1 到 maxn 之间的数字,映射到哈希数组中;
        }
        for(i = 1; i <= numsSize; ++i) {
            if(hash[i] < cases) {
                return i;                       // (2) 然后从 1 开始遍历哈希数组,第一个没有被哈希的就是答案;
            }
        }
        return numsSize + 1;                    // (3) 所有数字都遍历完毕,仍然没有找到,则答案为 n+1;    
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 已结题 (查看结题原因) 12月20日
  • 已采纳回答 12月20日
  • 创建了问题 12月20日

悬赏问题

  • ¥15 (标签-STM32|关键词-智能小车)
  • ¥20 关于#stm32#的问题,请各位专家解答!
  • ¥15 (标签-python)
  • ¥15 第一个已完成,求第二个做法
  • ¥20 搭建awx,试了很多版本都有错
  • ¥15 java corba的客户端该如何指定使用本地某个固定IP去连接服务端?
  • ¥15 activiti工作流问题,求解答
  • ¥15 有人写过RPA后台管理系统么?
  • ¥15 Bioage计算生物学年龄
  • ¥20 如何将FPGA Alveo U50恢复原来出厂设置哇?