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

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

力扣 https://leetcode-cn.com/problems/first-missing-positive/

写回答
好问题提建议
追加酬金
关注问题
分享
邀请回答

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；    
}

解决无用

打赏举报

报告相同问题？

提交关注问题

相关推荐更多相似问题

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数 leetcode 动态规划
2021-12-20 11:38

回答 1 已采纳一、分析思路如下： 1）如果在 1 到 maxn 之间的数字，映射到哈希数组中； 2）然后从 1 开始遍历哈希数组，第一个没有被哈希的就是答案； 3）所有数字都遍历完毕，仍然没有找到，则答案为 $n
给定一个数组和一个目标整数 java
2021-11-25 10:51

回答 2 已采纳 private static int [] m(int[] arr , int target){ Map<Integer,Integer> map = new Hash
给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素 leetcode 算法
2021-12-19 15:24

回答 1 已采纳 int swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; return tmp; } int remov
算法：给定一个未排序的整数数组，找出最长连续序列的长度
2020-04-09 16:09

加班狗的微博的博客给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为O(n)。二、思路通过将数组中的数字放入set中，然后遍历数组，查找set中是否有连续的序列三、实现 public static int ...
数组中未出现的最小正整数
2021-02-05 08:32

好吃还得是柚子的博客给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。要求：解决方案实现时间复杂度为 O(n) 并且只使用常数级别额外空间。本地编译器运行代码如下： #include<iostream> using ...
算法面试题：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
2020-09-09 09:24

我准备起飞的博客你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。提示：给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] 分析：数组中同一个元素不能使用...
leetcode算法题：给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数，我自己运行结果是正确的，在leetcode就不对了 javascript leetcode 算法
2022-03-08 15:18

回答 2 已采纳你可以看leetcode的最后一条信息提示，让你不要返回任何值，并且在适当的时候改变nums对象的值。你上面的做法只是让返回的值变成了符合答案的标准，而你的最初始nums数组对象只在你的第一步被反转的
解释一下那个nums +是什么意思 c语言数据结构算法
2022-03-09 17:41

回答 1 已采纳此处是单独写nums是表示nums的首地址，nums + left是表示第left个元素的地址nums + right同理由于swap函数是通过两个参数的地址将这两个值互换，所以需要传入第left和第
我想格式化一个整数数组。如何发送数组，以便每个动词接收数组的不同元素？
2019-06-07 18:32

回答 1 已采纳 You either need to pass in the elements individually: nums := []int{10,100,250,99} format := "%02
【数据结构与算法】之深入解析“下一个排列”的求解思路与算法示例
2022-01-26 16:09

╰つ栺尖篴夢ゞ的博客整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。如果不存在下一...
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
2020-05-11 15:22

kelley_luxuiary的博客给定一个按照升序排列的整数数组nums，和一个目标值target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是O(logn) 级别。如果数组中不存在目标值，返回[-1, -1]。示例 1: 输入: ...
2022-01-18：将数组分成两个数组并最小化数组和的差。给你一个长度为 2 * n 的整数数组。你需要将 nums 分成两个长度为 n 的数组，分别求出两个数组的和，并最小化两个数组和之
2022-01-18 22:10

福大大架构师每日一题的博客给你一个长度为 2 * n 的整数数组。你需要将 nums 分成两个长度为 n 的数组，分别求出两个数组的和，并最小化两个数组和之差的绝对值。nums 中每个元素都需要放入两个数组之一。请你返回最小的数组和之差。...
将整数数组中的数字连接成Golang中的一个数字？ [重复]
2017-06-23 20:38

回答 5 已采纳 I appreciate @KelvinS' approach, there already exists a math.Pow (though it deals in float64s. Ne
leetcode算法题：第一个唯一数字 c++
2021-06-11 20:22

回答 2 已采纳已解决
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 c语言
2021-10-03 21:11

回答 2 已采纳等等，我来 void moveZeroes(int[] nums) { // 0 边界处理 if (nums == null || nums.length ==0)
给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
2021-03-02 17:30

,,,, ,的博客 class Solution { public int maximumProduct(int[] nums) { //先排序 Arrays.sort(nums); int n = nums.length;...int a = Math.max(nums[0]*nums[1]*nums[n-1],nums[n-1]*nums[n-2]*nums[n-3]); return a; } }
未出现的最小正整数
2020-09-30 13:33

IT信息教室的博客给定一个未排序的整数列表，找出其中没有出现的最小的正整数，给定列表中可能包含重复的元素。要求算法是时间复杂度是O(n)，空间复杂度是O(1)。测试样例 # Input: [3, 4, -1, 1, 2, 2, 5] # Output: 6 # 列表长度...
三数之和给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组（GO，PHP）
2021-02-25 10:33

声嘶喑哑的博客给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。示例1 ：输入：nums = [-1,0,1,...
限制头文件#include<stdio.h> 一个整型数组中（数组长度不超过20）除了两个数字之外，其他的数字都出现了两次。请写程序找出这2个只出现一次的数字。 c语言
2020-04-21 22:16

回答 1 已采纳 ``` #include int main(){ int n; int arr1[20]; int arr2[20]; int curr = 0; scanf("%d",
【LeetCode】数组nums包含从0到n的所有整数，但其中缺了一个，请找出那个缺失的整数（面试题 17.04. 消失的数字）| 数组
2021-07-29 11:53

CodeWinter的博客文章目录@[TOC]1、题目描述：2、解题方法...先将数组中的数由小到大排序，再遍历排序后的结果，如果遍历下标和该下标对应的元素不相等，则返回该下标，如果遍历结束仍然没有符合条件，说明是最后一个数字 n 缺失了，则.
没有解决我的问题, 去提问

码龄粉丝数原力等级 --

莫比乌斯反演

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

1条回答默认最新

码龄粉丝数原力等级 --

一、分析

二、源码

相关推荐更多相似问题

码龄粉丝数原力等级 --

码龄粉丝数原力等级 --

码龄粉丝数原力等级 --

莫比乌斯反演

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

1条回答 默认 最新

一、分析

二、源码

相关推荐 更多相似问题

1条回答默认最新

相关推荐更多相似问题