首页 > 试题广场 >

缺失的第一个正整数

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

热度指数：76078 时间限制：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]

输出

算法知识视频讲解

Java

小灰灰QAQ

  public int minNumberDisappeared (int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        int j = 1;
        while (set.contains(j)){
            j++;
        }
        return j;
    }

发表于 2021-11-23 13:58:51 回复(0)

Java

草莓味的风

import java.util.*;
public class Solution {
    /*
    方法一：将数组中出现过的元素添加到一个hashmap中，并记录数组中的最大值
    然后从i从1加到n，依此判断i是否载hashmap中出现过，如果hashmap中没有出现过，直接返回这个数字。
    如果都出现过，就返回n+1。
    空间复杂度：O(n)，时间复杂度：O(n)
    */
    public int minNumberDisappeared (int[] nums) {
        // write code here
        if(nums==null||nums.length==0){
            return -1;
        }
        HashMap<Integer,Integer> hashmap = new HashMap<Integer,Integer>();
        for(int i=0;i<nums.length;i++){
            hashmap.put(nums[i],1);
        }
         
        for(int i=1;i<nums.length;i++){
            if(!hashmap.containsKey(i)){
              return i;
          }
        }
        return nums.length+1;
    }

    
    /*
    方法二：假设数组长度为n，那么缺失的数不是1-n，就是n+1
    因为是寻找缺失的最小正整数，所以可以先把数组中的负数和零移除出查找范围，将其改为n+1。
    以[-2,3,4,1,5]为例，改成[6,3,4,1,5]
    然后再遍历数组，如果nums[i]小于等于n，将nums[i]-1对应的下标上的值改为负数，表示该位置的正整数已经出现
    对于上面的数组，n=5：
    i=0时，nums[i]=6,没有更改
    i=1时，nums[i]=3,将数组下标为2的数值改为负数，即[6,3,-4,1,5]，表示3已经出现过了
    i=2时，nums[i]=4,将数组下标为3的数值改为负数，即[6,3,-4,-1,5]，表示4已经出现过了
    i=3时，nums[i]=1,将数组下标为0的数值改为负数，即[-6,3,-4,-1,5]，表示1已经出现过了
    i=4时，nums[i]=5,将数组下标为4的数值改为负数，即[-6,3,-4,-1,-5]，表示5已经出现过了
    然后再遍历数组，遇到的第一个大于零的数，证明该下标位置的数字没有出现过，返回下标+1
    否则证明1-n的数都出现过，返回n+1即可。
    最后，对于[-6,3,-4,-1,-5]，因为下标为0,2,3,4的位置上都是负数，证明1,3,4,5都出现过
    nums[1]=3是出现的第一个大于零的数，证明该下标所代表的数字没有出现过，该下标为1，代表的数字是2。
    返回2。
    */
    public int minNumberDisappeared (int[] nums) {
        for(int i=0;i<nums.length;i++){
            if(nums[i]<=0){
                nums[i] = nums.length+1;
            }
        }
        for(int i=0;i<nums.length;i++){
            int x = Math.abs(nums[i]);
            if(x <= nums.length){
                nums[x-1] = (-1) * Math.abs(nums[x-1]);
            }
        }
        for(int i=0;i<nums.length;i++){
            if(nums[i] > 0){
                return i+1;
            }
        }
        return nums.length+1;
    }
}

编辑于 2021-10-20 17:46:46 回复(1)

Java

LL.C

public int minNumberDisappeared (int[] nums) {
        // write code here
        Arrays.sort(nums);
        int res = 1;
        for(int i = 0;i < nums.length;i++){
            if(nums[i] == res){
                res++;
            }
        }
        return res;
    }

发表于 2022-08-25 14:17:28 回复(2)

Java

ITwolffy

public class Solution {
    public int minNumberDisappeared (int[] nums) {
        int n = nums.length;
        //原地交换[1,n]区域的数字x到x-1位置
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int j = nums[i] - 1;
                swap(nums, i, j);
            }
        }
        //遍历数组，如果i位置的数不是i+1，则就是最小缺失的正整数
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        //否则就是n+1
        return n + 1;
    }
    
    void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

发表于 2022-07-01 20:46:28 回复(0)

JavaScript Node

summer_swilder

function minNumberDisappeared( nums ) {
let obj = {};
for (let i = 0; i<nums.length; i++) {
obj[nums[i]] = 1;

}

let i = 1;

while (obj[i]) {
i++;
}
return i;
}
module.exports = {
minNumberDisappeared : minNumberDisappeared
};

发表于 2022-04-22 22:56:37 回复(0)

xxining

class Solution {
public:
    int minNumberDisappeared(vector<int>& nums) {
        int n = nums.size();
        for(int i=0;i<n;++i){
            while(nums[i]>0 && nums[i]<=n && nums[i]!=i+1){
                swap(nums[i],nums[nums[i]-1]);
            }
        }
        for(int i=0;i<n;++i){
            if(nums[i]!=i+1) return i+1;
        }
        return n+1;
    }    
};

发表于 2021-12-19 12:46:10 回复(0)

C++

sudo_root

    int minNumberDisappeared(vector<int>& nums) {
        // write code here
        sort(nums.begin(),nums.end());
        int res = 1;
        for(int i = 0;i < nums.size();i ++){
            if(nums[i] > 0 && nums[i] != res){
                return res;
            }
            else if(nums[i] > 0 && nums[i] == res){
                res++;
            }
        }
        
        return res;
    }

发表于 2021-11-02 19:50:49 回复(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)

Java

牛客839384289号

public int minNumberDisappeared (int[] nums) {
    // write code here
    Arrays.sort(nums);
    int res=1;
    for(int i=0;i<nums.length;i++){
        if(nums[i]<=0){
            continue;
        }
        if(res!=nums[i]){
            return res;
        }else{
            res++;
        }
    }
    return res;
}

发表于 2024-03-03 15:35:52 回复(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)

小刘新鲜事儿

import java.util.*;
import java.util.stream.Collectors;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */

    public int minNumberDisappeared(int[] nums) {
        
        Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toSet());
        int i=1;
        while (set.contains(i)){
            i++;
        }
        return i;
    }
}

发表于 2023-05-03 11:42:17 回复(1)

C++

牛客541678616号

class Solution {
public:
    int minNumberDisappeared(vector<int>& nums) {
        int res=1;
        sort(nums.begin(),nums.end());
        for(int x:nums)
        {
            if(x<=0)continue;
            if(x==res)res++;
            else
                return res;;
        }
        return res;
    }
};

发表于 2023-03-26 15:03:57 回复(0)

帅奶哟。

int minNumberDisappeared(int* nums, int numsLen ) {
    // write code here

    //缺失的第一个正整数只可能在1~500001中取
    int a[500001];
    int i;

    //遍历nums并在a中记录
    for (i = 0; i < numsLen; i++){  
        if (nums[i] > 0 && nums[i] <=500000) a[nums[i]]++;
    }
    //找到第一个出现次数为0的下标
    for (i = 1; i < 500001; i++){
        if (a[i] == 0) return i;
    }
    //前500000个数字没有，那么只可能是500001了
    return 500001;
}

发表于 2023-03-17 19:30:40 回复(1)

C++

Spectre_

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int minNumberDisappeared(vector<int>& nums) {
        // 时间复杂度O(N)，空间复杂度O(1)
        int n = nums.size();
        for (int &num : nums) if (num <= 0) num = n + 1;
        for (int &num : nums) if (num <= n) nums[abs(num) - 1] *= -1;
        for (int i = 0; i < n; ++i) if (nums[i] > 0) return i + 1;
        return n + 1;
    }
};

发表于 2022-10-13 17:05:47 回复(0)

Python 3

Vivimore

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

发表于 2022-06-18 20:50:36 回复(1)

Java

***

1首先确定数组数目
2自定义一个标识数组，以数据值为索引，值为1则存在这个数，为0就不存在
3 遍历标识数组，碰到为0直接返回索引值，如果全为1,则返回数据数组长度+1


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int minNumberDisappeared (int[] nums) {
        // write code here
       int[] data=new int[nums.length+1];
        Arrays.fill(data,0);
        for(int i=0;i<nums.length;i++){
            if(nums[i]>=0&&nums[i]<=nums.length){
                data[nums[i]]=1;
            }
        }
        for(int i=1;i<data.length;i++){
            if(data[i]==0){
                return i;
            }
        }
        return nums.length+1;
        
       
    }
}

发表于 2022-03-18 18:23:55 回复(0)

Java

牛客906920838号

import java.util.*;

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return int整型
*/
public int minNumberDisappeared (int[] nums) {
int minNumber =1;
Arrays.sort(nums);
for(int i =0; i<nums.length;i++){
if(nums[i]>=0 && nums[i] == minNumber){
minNumber++;
}
}
return minNumber;
}
}

发表于 2021-11-27 15:40:29 回复(0)

Java

崔家乐

import java.util.*;


public class Solution {
    public int minNumberDisappeared (int[] nums) {
        int[] arr = new int[nums.length+2];
        for(int i =0; i < nums.length; i++){
            if(nums[i]>0&&nums[i]<arr.length){
                arr[nums[i]] = i+1;
            }
        }
        int i = 1;
        while(arr[i]!=0){
            i++;
        }
        return i;
    }
}

发表于 2021-11-01 10:37:22 回复(1)

C++

不经历怎么能成长

class Solution {
public:
    int minNumberDisappeared(vector<int>& nums) {
        // 原地哈希
        int len = nums.size();
        for(int i=0; i<len; i++){
            if(nums[i] <= len && nums[i] > 0 && nums[nums[i]-1]!=nums[i]){
                swap(nums[nums[i]-1], nums[i]);
                i--;
            }
        }
        int ans = len+1;
        for(int i=0; i<len; i++){
            if(nums[i]!=i+1) {ans = i+1; break;}
        }
        return ans;
    }
};

发表于 2021-09-27 16:46:00 回复(0)

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)

提交观点

问题信息

数组哈希

上传者：牛客301499号

难度：

145条回答 629收藏 4214浏览

通过挑战的用户

查看代码

牛客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

缺失的第一个正整数

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题