牛客热题：数组中出现一次的两个数字> 📟作者主页：慢热的陕西人

🌴专栏链接：力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏，🍉留言

牛客热题：缺失的第一个正整数

题目链接

缺失的第一个正整数_牛客题霸_牛客网 (nowcoder.com)

方法一：排序

思路

• step1： 先将数组进行排序
• step2：引入一个计数count = 1；
• step3：当数组大于零的时候并且当前遍历的值等于count的时候–count++
• step4: 当遍历的数组元素已经大于count了，这时候退出循环，代表已经找到了对应的缺失的整数

代码

    int minNumberDisappeared(vector<int>& nums) 
    {
        int count = 1;
        
        sort(nums.begin(), nums.end());

        for(auto num : nums)
        {
            if(num > 0)
            {
                if(count == num)
                {
                    count++;
                }
                else if(count < num)
                {
                    break;
                }
            }
        }

        return count;
    }

复杂度

时间复杂度：O($NlogN$) , 排序的时间复杂度近似为$NlogN$， 然后遍历了一遍数组

空间复杂度：O(1), 使用了常数个变量

方法二：哈希表

思路

step1：将数组中的所有元素全部放入到哈希表

step2：然后从1开始遍历哈希表不存在就结束

代码

    int minNumberDisappeared(vector<int>& nums) 
    {
        unordered_map<int, int> hash;

        for(auto num : nums)
        {
            hash[num]++;
        }

        int res = 1;
        while(hash[res]) res++;

        return res;
    }

复杂度

时间复杂度：O(N) , 遍历了一遍数组，然后遍历了部分哈希表

空间复杂度：O(N) , 使用了哈希表的额外空间

方法三：原地哈希

思路

1. 数组长度和值范围：
   • 一个长度为 n 的数组可以包含 n 个元素。
   • 如果数组中包含从 1 到 n* 的所有正整数，那么这 n* 个元素正好能填满整个数组。
2. 最小的缺失正整数：
   • 如果数组中包含了所有 1 到 n* 的数，那么下一个正整数就是 n+1。
   • 如果数组中缺少某个数，那么这个缺失的数一定在 1 到 n 之间。
3. 极端情况：
   • 如果数组中的数全部大于 n 或者非正（如 0 或负数），那么最小的缺失正整数就是 1，因为没有任何数在 1 到 n* 之间。

具体做法：

• step 1：我们可以先遍历数组将所有的负数都修改成n+1。
• step 2：然后再遍历数组，每当遇到一个元素绝对值不超过n时，则表示这个元素是1～n中出现的元素，我们可以将这个数值对应的下标里的元素改成负数，相当于每个出现过的正整数，我们把与它值相等的下标都指向一个负数，这就是类似哈希表的实现原理的操作。
• step 3：最后遍历数组的时候碰到的第一个非负数，它的下标就是没有出现的第一个正整数，因为它在之前的过程中没有被修改，说明它这个下标对应的正整数没有出现过。

代码

int minNumberDisappeared(vector<int>& nums) {
        int n = nums.size();
        //遍历数组
        for(int i = 0; i < n; i++) 
            //负数全部记为n+1
            if(nums[i] <= 0) 
                nums[i] = n + 1;
        for(int i = 0; i < n; i++)
            //对于1-n中的数字
            if(abs(nums[i]) <= n) 
                //这个数字的下标标记为负数
                nums[abs(nums[i]) - 1] = -1 * abs(nums[abs(nums[i]) - 1]); 
        for(int i = 0; i < n; i++)
            //找到第一个元素不为负数的下标
            if(nums[i] > 0)
                return i + 1;
        return n + 1;
    }

复杂度

从代码中可以看到，除了输入数组 nums 之外，算法没有使用额外的存储空间（只用了一些常数空间用于变量 i 和 n）。因此空间复杂度主要取决于输入数组。

由于算法就地（in-place）修改输入数组 nums，没有使用任何额外的存储空间，空间复杂度为 �(1)O(1)。

总结

• 时间复杂度：O(n)
• 空间复杂度：O(1)