首页 > 试题广场 >

缺失的第一个正整数

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

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

风雨尘

public int minNumberDisappeared (int[] nums) {
    // write code here
    if (nums == null || nums.length == 0) return -1;

    Arrays.sort(nums);
    
    int min = 1;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] < 1) {
            continue;
        } else if (nums[i] == min) {
            min++;
            continue;
        }
    }
    return min;
}

编辑于 2024-04-16 11:33:43 回复(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)

Java

丶Clearlove

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


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int minNumberDisappeared (int[] nums) {
        List<Integer> collect = Arrays.stream(nums).boxed()
                                .filter(item -> item > 0)
                                .sorted(Comparator.naturalOrder())
                                .collect(Collectors.toList());
        boolean isFirst = true;
        if (collect.size() == 0) {
            return 1;
        } else if (collect.size() == 1) {
            return (collect.get(0) != 1) ? 1 : 2;
        }
        for (int i = 0; i < collect.size() - 1; i++) {
            int val1 = collect.get(i);
            int val2 = collect.get(i + 1);
            if (isFirst && val1 > 1) return 1;
            if (val2 - val1 > 1) return val1 + 1;
            isFirst = false;
            if (i == collect.size() - 2) return val2 + 1;
        }
        return 1;
    }
}

发表于 2024-01-17 22:13:12 回复(0)

Java

加勒比海涛

import java.util.*;


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

        // 2. 对数组进行排序
        Arrays.sort(nums);

        // 3. 创建 ans 表示缺失的第一个正数
        // 初始化成 1
        int ans = 1;

        // 4. 遍历数组
        for (int x : nums) {
            // 如果当前元素 == res,那就代表当前正整数出现过
            if (x == ans) {
                ans++;
            }
        }

        // 5. 最后返回 ans 的值
        return ans;
    }
}

发表于 2023-09-09 09:40:54 回复(0)

Java

做则必成的勇气和信心

public int minNumberDisappeared (int[] nums) {
        // 缺失的  最小  正 正数  所以最小的结果只可能是1
        //先存入Map,
        //再遍历Map
        if(nums==null||nums.length==0) return -1;
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            map.put(nums[i],1);//map存的  k-number[i]  v-1
        }
        int ans=1;
        for(int i=0;i<map.size();i++){//遍历map
            if(map.containsKey(ans)){//这里的containsKey(ans)  括号中是ans
                ans++;
            }
        }
        return ans;
    }

发表于 2023-07-14 15:22:51 回复(0)

Java

诸葛潇洒

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int minNumberDisappeared (int[] nums) {
        int i = 0;
        int j = 0;
        while (i < nums.length && j < nums.length) {
            if (nums[j] == i + 1) {
                //找到了当前位置下的数字
                swap(nums, i, j);
                ++i;
                j = i;
            } else {
                ++j;
            }
        }
        return i + 1;
    }

    void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

发表于 2023-05-24 23:39:36 回复(0)

Java

Hmk

/**

* @param nums int整型一维数组

* @return int整型

public static int minNumberDisappeared (int[] nums) {

// write code here

// 1.HashSet

TreeSet<Integer> set = new TreeSet<>();

for (int i = 0; i < nums.length; i++) {

set.add(nums[i]);

}

for (int i = 1; i < nums.length; i++) {

// 直接返回最小正整数i

if (!set.contains(i)) {

return i;

}

if (!set.isEmpty() && set.last() > 0)

return set.last() + 1;

else

// 负数或 0

return 1;

}

public static void main(String[] args) {

int[] in = new int[] {-2, -1, 1, 0, 2, 3, 4, 5};

System.out.println(minNumberDisappeared(in));

}

发表于 2023-03-11 17:05:04 回复(0)

Java

牛客585981974号

public int minNumberDisappeared (int[] nums) {
        int temp = 0;
        ArrayList<Integer> arr = new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            arr.add(nums[i]);
        }
        Collections.sort(arr);
        for(int i=0;i<arr.size();i++){
            if(arr.get(i) == temp+1){
                temp = arr.get(i);
            }
        }
        return temp+1;
    }

发表于 2023-03-10 16:31:31 回复(0)

Java

WangShi10

public int minNumberDisappeared (int[] nums) {

// write code here

for(int i=0; i<nums.length; i++) {

if(nums[i] > 0 && nums[i] <= nums.length && nums[i] != i+1) {

int tmp = nums[i];

nums[i] = nums[tmp-1];

nums[tmp-1] = tmp;

i--;

}

for(int i=0; i<nums.length; i++) {

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

return i+1;

}

return nums.length + 1;

}

发表于 2023-03-06 22:38:52 回复(0)

Java

小杨yyy

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int minNumberDisappeared (int[] nums) {
        // write code here
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            map.put(nums[i],1);//用hashMap存储nums中的元素
        }
        int res=1;
        for(int i=0;i<map.size();i++){
            if(map.containsKey(res)){
                res++;//如果res都存在与map的key中，则1到res的值都存在，返回res+1即可，如果第一次不存在于hashMap中，则返回第一次的res值
            }
        }
        return res;
    }
}

发表于 2022-11-12 22:01:34 回复(0)

Java

牛客223501547号

 public int minNumberDisappeared (int[] nums) {
                  Arrays.sort(nums);
            for(int i=1;i<nums.length+2;i++){
               int a = Arrays.binarySearch(nums,i);
              if(a<0){
                  return i;
              }
            }
          return 0;
    }
太简单了，不会有人不会吧

发表于 2022-10-28 20:34:46 回复(0)

Java

是小王吖🐅

import java.util.*;


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

发表于 2022-09-10 21:05:40 回复(0)

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

qv123

publicclassSolution {

publicintminNumberDisappeared (int[] nums) {

Set<Integer> set=newHashSet<>();

for(intnum:nums){

set.add(num);

}

inti=1;

while(true){

if(set.contains(i)){

i++;

}else{

break;

}

returni;

}

发表于 2022-08-12 21:53:11 回复(0)

Java

yxjing

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int minNumberDisappeared (int[] nums) {
        // write code here
        List<Integer> list=new ArrayList<Integer>();
        for(int i=0;i<=nums.length-1;i++){
            list.add(nums[i]);
        }
        Collections.sort(list);
        
        int k=-1;
        for(int i=0;i<=nums.length-1;i++){
            if(list.get(i)>0){
                k=i;
                break;
            }
        }
        
        if(k==-1){return 1;}//即其中无正数
        else if(list.get(k)>1){return 1;}//即第一个正数不是1
        else{//即第一个正数是1
            while(k!=nums.length-1&&(list.get(k+1)==list.get(k)+1||list.get(k+1)==list.get(k))){
                k++;
            }
            return list.get(k)+1;
        }
   
    }
    
}

发表于 2022-08-02 20:50:13 回复(0)

提交观点

问题信息

数组哈希

上传者：牛客301499号

难度：

52条回答 632收藏 4255浏览

通过挑战的用户

查看代码

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

缺失的第一个正整数

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题