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

给你一个未排序的整数数组 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;    
    }
    
    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题