我要招人

去企业版

首页 > 试题广场 >

缺失的第一个正整数

[编程题]缺失的第一个正整数

热度指数：76755 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个无重复元素的整数数组nums，请你找出其中没有出现的最小的正整数

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

数据范围:

$-2^{31}\le nums[i] \le 2^{31}-1$

$0\le len(nums)\le5*10^5$

示例1

输入

[1,0,2]

输出

示例2

输入

[-2,3,4,1,5]

输出

示例3

输入

[4,5,6,8,9]

输出

算法知识视频讲解

Python3

偷时间的賊

思路是一共是len(nums）个元素，直接遍历一遍，刚好下标i就是遍历的正整数，看i是否在nums，不在就直接输出，如果一直在的话，就输出下一个整数。

有一点是不去重的话会超时！

class Solution:
    def minNumberDisappeared(self , nums: List[int]) -> int:
        # write code here
        num_set = set(nums)
        for i in range(1, len(num_set)):
            if i not in num_set:
                return i
        return len(nums)+1

发表于 2024-04-17 21:00:22 回复(0)

Python3

川流不息憨憨

class Solution:
    def minNumberDisappeared(self , nums: List[int]) -> int:
        # write code here
        nums.sort()
        ans = 1
        for i in nums:
            if ans == i:
                ans += 1
        return ans

编辑于 2024-03-19 21:33:24 回复(0)

Python3

Anzer

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def minNumberDisappeared(self , nums: List[int]) -> int:
        # write code here
        min_num = 1
        nums.sort()
        for n in nums:
            # 如果出现的值和当前相等，则最小值+1
            if n == min_num:
                min_num += 1
            # 若比最小值大，则当前记录的最小值就是最小值
            elif n > min_num:
                return min_num
        return min_num

编辑于 2024-01-16 22:36:56 回复(0)

Python3

牛客465309906号

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def minNumberDisappeared(self , nums: List[int]) -> int:
        # write code here
        num = set(nums)
        for i in range(1, len(num)):
            if i in num:
                continue
            return i
        return len(num)+1

发表于 2023-08-17 15:15:42 回复(0)

Python3

还记得你最初的梦想吗

将nuns转化为字典，然后遍历查询是否在字典李就可以

def minNumberDisappeared(self , nums: List[int]) -> int:
    # write code here
    nums = set(nums)
    i = 1
    while i in nums:
        i += 1
        return i

发表于 2023-05-05 14:47:36 回复(1)

Python3

Lxyapc

def minNumberDisappeared(self , nums: List[int]) -> int:

# write code here

# 解题思路：题中给出数组无重复元素，我们可以先把每个元素放在对应的位置上，

# 也就是 nums[i] 中放置 i+1，因为下标从0开始。

# 然后再遍历整个数组，哪个位置的元素不在其位，判定其缺席。

# 如果各在其位，则超出数组以外的缺席。

m = len(nums)

for i in range(m):

while (1 <= nums[i] < m and nums[i] != i+1):

#判断如果不在其位，则将其换到应该在的位置：

#nums[i]，应该在放在 nums[i]-1的位置上

#用while而不是if，是因为换回来的数字不一定是正确的，

#while保证流程完善，回来的数字要么是正确的，要么不在[1,n]范围内。

nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]

#此处使用Python特有的元组赋值法，如上

#也可按照通用的临时变量暂存，相互交换的方式放置，

#如果用三变量交换法，一定写成下面样

# k = nums[nums[i]-1]

# nums[nums[i]-1] = nums[i]

# nums[i] = k

#而不可写成下面样子。。。难道不一样么，仔细思考一下为什么

# k = nums[i]

# nums[i]=nums[nums[i]-1]

# nums[nums[i]-1] = k

for i in range(m): #遍历数组，最开始找到不在其位就是最小的正整数

if(nums[i] != i+1):

return i+1

return m+1

#如果遍历数组后，各在其位，说明数组是一条龙。。。最小的正整数超出范围

发表于 2023-03-10 20:58:36 回复(0)

Python3

曰无衣bupt

这里可以用不太常见的for...else语句做，虽然下面的解法超时了，但思路可以借鉴。

class Solution:
    def minNumberDisappeared(self , nums: List[int]) -> int:
        # write code here
        n = [i for i in range(1, max(nums))]
        for i in n:
            if i not in nums:
                return i
        else:
            return max(nums)+1

发表于 2023-01-27 21:18:59 回复(0)

Python3

JianYue

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def minNumberDisappeared(self , nums: List[int]) -> int:
        exists = set()
        for i in nums:
            if i > 0:
                exists.add(i)
        ret = 1
        while True:
            if ret in exists:
                ret = ret + 1
                continue
            return ret

发表于 2022-09-24 16:40:16 回复(0)

Python3

ZirconiumZr

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def minNumberDisappeared(self , nums: List[int]) -> int:
        temp = []
        for i in range(len(nums)):
            if nums[i]>0:
                temp.append(nums[i])
        temp.sort()
        for j in range(len(temp)):
            if temp[j] != j+1:
                return(j+1)
            elif j == (len(temp)-1):
                return(j+2)

发表于 2021-12-12 18:03:41 回复(0)

提交观点

问题信息

数组哈希

上传者：牛客301499号

难度：

11条回答 632收藏 4257浏览

通过挑战的用户

查看代码

牛客89418...

2022-10-27 16:32:27
牛客86531...

2022-09-16 18:53:41
Daoremi

2022-09-16 17:29:06
粗茶

2022-09-16 17:03:01
牛客13682...

2022-09-16 16:52:44

缺失的第一个正整数

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题