CS-Wiki CS-Wiki
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
  • 刷题模板汇总
  • 一些刷题小技巧
  • 整数 and 位运算

  • 数组

  • 链表

  • 哈希表

    • 哈希表理论基础
    • 剑指 Offer 50 - 第一个只出现一次的字符
    • 验证外星语词典
    • 有效的字母异位词
    • 字母异位词分组
    • 单词长度的最大乘积
    • 两个数组的交集
    • 多个数组求交集
    • 赎金信
    • 快乐数
    • 两数之和
    • 四数相加 II
    • 最小时间差
    • 缺失的第一个正数
      • 📃 题目描述
      • 🔔 解题思路
      • 💥 复杂度分析
    • 最长连续序列
    • 剑指 Offer 03 - 数组中重复的数字
    • 利用哈希表设计高级结构

  • 字符串

  • 栈

  • 队列

  • 二叉树

  • 前缀树

  • 二分查找

  • 双指针法

  • 区间求和问题

  • 排序

  • 回溯算法

  • 贪心算法

  • 动态规划

  • 图

  • 数学

  • 自动机

  • 海量数据和空间限制

  • 05-数据结构与算法
  • 哈希表
小牛肉
2022-08-03
目录

缺失的第一个正数

# 📃 题目描述

题目链接:41. 缺失的第一个正数 (opens new window)

# 🔔 解题思路

可以马上想到用 HashMap 存 nums,然后从整数 1 开始遍历,第一个在 Map 中找不到的数就是第一个缺失的正整数,但是这种做法的空间复杂度是 O(N)

想要空间复杂度 O(1),可以用数组来代替哈希表

即下标为 i 存储整数 i + 1(之所以不用下标 i 存储整数 i,是因为这道题目显然不需要 0 这个数)

  • 由于题目要求我们「只能使用常数级别的空间」,而要找的数一定在 [1, N + 1] 左闭右闭(这里 N 是数组的长度)这个区间里。因此,我们可以就把原始的数组当做哈希表来使用。事实上,哈希表其实本身也是一个数组;
  • 我们要找的数就在 [1, N + 1] 里,最后 N + 1 这个元素我们不用找。因为在前面的 N 个元素都找不到的情况下,我们才返回 N + 1;
  • 那么,我们可以采取这样的思路:就把 1 这个数放到下标为 0 的位置, 2 这个数放到下标为 1 的位置,按照这种思路整理一遍数组。然后我们再遍历一次数组,第 1 个遇到的它的值不等于下标的那个数,就是我们要找的缺失的第一个正数。
class Solution {
    public int firstMissingPositive(int[] nums) {
        // corner case
        if (nums == null || nums.length == 0) {
            return 1;
        }

        int i = 0;
        while (i < nums.length) {
            // nums 作为哈希表只能存储 [1, nums.length] 的数
            if (nums[i] <= 0 || nums[i] == i + 1 || nums[i] > nums.length) {
                i ++;
                continue;
            }
            // nums[i] >= 0 && nums[i] != i + 1 && nums[i] <= nums.length
            int index = nums[i] - 1;
            // nums[i] 和 nums[index] 交换
            if (nums[index] != nums[i]) {
                swap(nums, i, index);
            }
            // 如果 nums[i] 已经等于 nums[index] 了,说明存在重复数(比如 [1, 1]),直接 i ++ 就行
            // 不 i++ 的话会陷入死循环
            else {
                i ++;
            }
        }

        for (int j = 0; j < nums.length; j ++) {
            if (nums[j] != j + 1) {
                return j + 1;
            }
        }
        
        // 前面的 N 个元素都找不到的情况下,返回 N + 1
        return nums.length + 1;
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

# 💥 复杂度分析

  • 空间复杂度:
  • 时间复杂度:

🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~

帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10
最小时间差
最长连续序列

← 最小时间差 最长连续序列→

最近更新
01
我掏出这个多线程轮子,面试官直接全体起立
04-13
02
面试官问你有其他 Offer 吗,该怎样回答
04-10
03
天不生陈志龙,职场万古如长夜
04-06
更多文章>
Theme by Vdoing | Copyright © 2019-2023 飞天小牛肉 | 皖ICP备2022008966号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式