nowcoder NC30 缺失的第一个正整数

比眉伴天荒 2023-10-15 23:49 41阅读 0赞

**目录**

题目描述：

分析：

完整代码：

--------------------

[题目链接： ![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://www.nowcoder.com/share/jump/819478881694767416272][_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_www.nowcoder.com_share_jump_819478881694767416272]

# 题目描述： #

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

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

> **示例1**
> 
> 输入：\[1,0,2\]
> 
> 返回值：3
> 
> **示例2**
> 
> 输入：\[-2,3,4,1,5\]
> 
> 返回值：2
> 
> **示例3**
> 
> 输入：\[4,5,6,8,9\]
> 
> 返回值：1

# 分析： #

当看完题目和所给的三个例子后我们可以得出以下结论：

1.  **所给数组中的数据是随机的整数且是无序的；**
2.  **所给数组中的数据有负数；**
3.  **返回值必须不小于 1 。**

题目要求的**空间复杂度 O(1)，时间复杂度 O(n)，**那么我们就应该**尽量减少空间的开辟。**

本题**可以使用哈希表但是**这样**空间复杂度就是O(n)了**所以这个方法应该是实在想不出解法了再使用。

那么此时我们就可以**从**上面得出的**结论入手**，既然数组是无序的那么我们就可以先使用库方法将其进行排序。

public int minNumberDisappeared (int[] nums) {
            Arrays.sort(nums);        
        }

当排好序之后我们的思路一下就打开了，此时由于**数组内可能会有不大于 0 的数**出现所以我们可以先用一个**循环来跳过这部分**：

public int minNumberDisappeared (int[] nums) {
            int ret = 0; //返回值
            int len = nums.length; //数组长度
            Arrays.sort(nums);
            int i = 0; //记录数组遍历的位置
    
            while (i < len && nums[i] <= 0) {
                i++;
            }
        }

此时数组就剩下不小于 0 的数了，此时再进行判断就非常简单了，我们就可以直接**判断两个数之间是否存在整数**如果存在就返回这个整数。**如果数组是 \[1,2,3,4\]** 这样的那么我们就**返回最后一个数加一。**

while (i < len - 1) {
                if (nums[i] + 1 < nums[i+1]) {
                    return nums[i] + 1;
                }
                i++;
            }
            ret = nums[len-1] + 1;
            return ret;

最后就到了每次做题都必不可少的环节了：**极限值判断**

再代码的最前面对数组进行判断：**如果数组不存在就返回最小的正整数 1** 。

if (nums == null || nums.length == 0) {
                return 1;
            }

在第一个循环之后判断如果**数组中没有 1 那么就返回 1** 。

if (nums[i] - 1 >= 1) {
                return 1;
            }

此时如果忽略库函数的复杂度那么本题我们所使用的复杂度就是：**空间复杂度 O(1)，时间复杂度 O(n)。**

![ee9cec1eec15429ca557f21cd43924c8.png][]

# 完整代码： #

import java.util.*;
    
    
    public class Solution {
    
        public int minNumberDisappeared (int[] nums) {
            // write code here
            if (nums == null || nums.length == 0) {
                return 1;
            }
            int ret = 0;
            int len = nums.length;
            Arrays.sort(nums);
            int i = 0;
    
            while (i < len && nums[i] <= 0) {
                i++;
            }
            if (nums[i] - 1 >= 1) {
                return 1;
            }
            while (i < len - 1) {
                if (nums[i] + 1 < nums[i+1]) {
                    return nums[i] + 1;
                }
                i++;
            }
            ret = nums[len-1] + 1;
            return ret;
        }
    }

[icon-default.png_t_N7T8]: https://csdnimg.cn/release/blog_editor_html/release2.3.6/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N7T8
[_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_www.nowcoder.com_share_jump_819478881694767416272]: https://www.nowcoder.com/share/jump/819478881694767416272
[ee9cec1eec15429ca557f21cd43924c8.png]: https://img-blog.csdnimg.cn/ee9cec1eec15429ca557f21cd43924c8.png