Leetcode 19 java

发布于：2025-09-15 ⋅ 阅读:(13) ⋅ 点赞:(0)

1 题目

448. 找到所有数组中消失的数字

提示

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：

输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]

示例 2：

输入：nums = [1,1]
输出：[2]

提示：

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= n

进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。


2 我的想法

一共是1到n的区间，从1取到n，长度也刚好是n。

存在消失的数，也就是对应找一下没有在1到n出现的数，直接hash？很笨的办法，循环比对这个数字是否出现过，如果重复出现了就说明有消失的。。。啊，不知道怎么弄！

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        
    }
}

3 关于我的想法

你的想法 “用 hash 表存数字、再循环比对 1 到 n 里没出现的数”，完全可行！ 先肯定你的思路 —— 这是最直接、最容易想明白的办法，一点都不 “笨”，反而很符合正常人解决问题的逻辑。

不过咱们可以拆解开，聊聊它的 “好” 和 “可以优化的地方”，帮你更清楚它的可行性边界：

1. 先讲你的思路具体怎么实现（帮你把想法落地）

你的核心逻辑是 “记录出现过的数，再找没记录的”，用 Java 的HashSet就能实现，步骤特别简单：

  • 第一步：把数组里所有数字都放进HashSet（因为HashSet不存重复值，刚好能自动过滤掉重复的数）；
  • 第二步：从 1 到 n 逐个检查 —— 如果某个数不在HashSet里，就说明它是 “消失的数”，把它放进结果里。

比如示例 1：nums = [4,3,2,7,8,2,3,1]

  • 第一步放进HashSet后，里面是{1,2,3,4,7,8}；
  • 第二步从 1 查到 8：发现 5、6 不在集合里，所以结果就是[5,6]，和题目要求完全一致。

2. 再聊可行性：优点很明显，也有个小 “代价”

优点（为什么可行）：
  • 逻辑简单：不用绕弯子，“存出现的→找没存的”，一眼就能看懂，写代码也不容易出错；
  • 时间能接受：HashSet的 “存” 和 “查” 操作都是 O (1)，整个过程要遍历数组（O (n)）+ 遍历 1 到 n（O (n)），总时间还是 O (n)，满足题目 “时间复杂度 O (n)” 的要求。
小 “代价”（为什么题目会有 “不使用额外空间” 的进阶要求）：
  • 需要额外的空间：HashSet最多要存 n 个数字（如果数组里没有重复），所以空间复杂度是 O (n)—— 这不符合题目 “进阶要求”，但完全符合基础要求，用来解决问题是没问题的。

3. 总结：你的想法 “能解决问题”，但可以更优

  • 可行性结论：100% 可行！用HashSet的实现能正确得出所有消失的数字，而且代码好写好懂；
  • 和最优解的区别：最优解（之前给你的 “负数标记法”）是利用数组本身做标记，不需要额外空间（空间 O (1)），而你的思路需要HashSet的额外空间（空间 O (n)）—— 但这只是 “优不优” 的区别，不是 “能不能用” 的区别。

按照这个思路实现的代码：

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        // 创建一个哈希集合，用来存数组中出现过的数字
        Set<Integer> seen = new HashSet<>();
        
        // 把数组里所有数字都放进集合（自动去重）
        for (int num : nums) {
            seen.add(num);
        }
        
        // 准备一个列表，用来存消失的数字
        List<Integer> result = new ArrayList<>();
        
        // 从1到n逐个检查，如果不在集合里，就是消失的数字
        for (int i = 1; i <= nums.length; i++) {
            if (!seen.contains(i)) {
                result.add(i);
            }
        }
        
        return result;
    }
}

这段代码的逻辑和你想的完全一致：

  1. 先用 HashSet 记住数组里出现过的所有数字（重复的会自动忽略）
  2. 然后从 1 到 n 一个一个检查，没在 HashSet 里的就是消失的数字
  3. 把这些消失的数字收集起来返回

比如输入 [4,3,2,7,8,2,3,1]：

  • 集合里会有 {1,2,3,4,7,8}
  • 检查 1 到 8 时，发现 5 和 6 不在集合里，就把它们加入结果

4 利用数组本身来做标记

问题是要找出 1 到 n 中那些没有出现在数组里的数字，其中 n 是数组的长度。

思路很巧妙：我们可以利用数组本身来做标记，这样就不用额外的空间了。

具体做法：

  1. 遍历数组中的每个数字
  2. 把这个数字对应的数组位置做个标记（表示这个数字存在）
  3. 最后再遍历一次，看看哪些位置没有被标记，那些位置对应的数字就是消失的数字

举个例子，如果你看到数字 3，就去把数组第 3 个位置（索引 2）的数改成负数，表示 3 存在。

下面是代码实现：

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        // 遍历数组中的每个数字
        for (int i = 0; i < nums.length; i++) {
            // 取当前数字的绝对值（因为可能已经被标记成负数了）
            int num = Math.abs(nums[i]);
            // 计算这个数字对应的索引位置（减1是因为数组从0开始）
            int index = num - 1;
            
            // 如果这个位置的数是正数，就把它变成负数，做个标记
            if (nums[index] > 0) {
                nums[index] = -nums[index];
            }
        }
        
        // 收集所有消失的数字
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            // 如果某个位置还是正数，说明对应的数字没出现过
            if (nums[i] > 0) {
                // 索引加1就是对应的数字
                result.add(i + 1);
            }
        }
        
        return result;
    }
}

这样解释是不是很清楚？这个方法既不用额外空间，又能在 O (n) 时间内完成，完全符合题目的进阶要求。

简单说就是：看到谁就给谁家里做个标记，最后没标记的家庭就是我们要找的。

5 原地修改法

核心思路和 “负数标记法” 类似，但用了 “加 n” 的方式来做标记，我用大白话给你解释下：

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        for (int num : nums) {
            int x = (num - 1) % n;
            if (nums[x] <= n) {
                nums[x] += n;
            }
        }
        List<Integer> ret = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            if (nums[i] <= n) {
                ret.add(i + 1);
            }
        }
        return ret;
    }
}

核心逻辑：用 “加 n” 做标记，区分 “出现过” 和 “没出现过”

数组长度是 n，数字范围是 1~n。

  • 如果某个数字num出现过，就给它对应位置（num-1）的数 “加 n”
  • 最后检查：如果某个位置的数没超过 n，说明对应的数字没出现过

分步拆解（拿示例 1 nums = [4,3,2,7,8,2,3,1] 举例）

  1. 第一次遍历：给出现过的数字做标记
    遍历每个数字num：

    • 计算它应该标记的位置：x = (num - 1) % n
      （取模是因为之前的数可能已经被加过 n 了，需要还原真实值）
    • 如果这个位置的数还没被标记（<=n），就给它加 n（变成>n，表示 “对应数字出现过”）

    比如：

    • 第一个数是 4 → 位置是 3 → nums[3]原本是 7 → 7+8=15（现在nums[3]=15，表示 4 出现过）
    • 第二个数是 3 → 位置是 2 → nums[2]原本是 2 → 2+8=10（表示 3 出现过）
    • ... 以此类推，最后数组会变成：[12, 19, 18, 15, 8, 2, 11, 9]

  2. 第二次遍历：找没被标记的位置
    遍历数组，看每个位置的数是否<=n：

    • 如果<=n，说明这个位置对应的数字没出现过（因为没被加过 n）
    • 位置 i 对应的数字是i+1，加入结果

    示例中：

    • 位置 4 的数是 8（<=8）→ 对应数字 5 没出现
    • 位置 5 的数是 2（<=8）→ 对应数字 6 没出现
    • 所以结果是[5,6]

为什么这样可行？

  • 不额外占空间：直接在原数组上修改，用 “加 n” 标记，不用 HashSet 或新数组
  • 时间 O (n)：两次遍历数组，效率很高
  • 标记不会冲突：原本的数最大是 n，加 n 后一定>n，能明确区分是否被标记

简单说就是：谁出现过，就给他 “老家”（对应位置）的数涨工资（加 n），最后没涨工资的 “老家”，就是没人回来过（数字没出现）～

【更详细地介绍以上标记法则】

先明确前提

  • 数组 nums 的长度是 n（比如示例 1 中 n=8）
  • 数组里的数字范围是 1~n（比如示例 1 中数字只可能是 1~8）
  • 我们要找的是 1~n 中没出现在数组里的数字

核心原理

用数组自己的位置来 “记录” 某个数字是否出现过：

  • 对于数字 num（1~n），它 “应该在” 的位置是 num-1（因为数组索引从 0 开始）
  • 如果 num 出现过，就给 num-1 这个位置的数 “加 n”（做个标记）
  • 最后，没被 “加 n” 的位置，对应的数字就是消失的数字

逐行解析代码（结合示例 1：nums = [4,3,2,7,8,2,3,1]，n=8）

第一步：第一次遍历数组，给出现过的数字做标记
int n = nums.length; // n=8（数组长度）
for (int num : nums) { // 遍历数组里的每个数字
    int x = (num - 1) % n; // 计算当前数字应该标记的位置
    if (nums[x] <= n) { // 如果这个位置还没被标记
        nums[x] += n; // 给这个位置的数加n（标记为“出现过”）
    }
}

我们一步一步走这个循环：

  1. 第一个数字 num=4：

    • 计算位置：x = (4-1) % 8 = 3 % 8 = 3（对应索引 3）
    • 检查 nums[3] 的值：原本是 7（7 <= 8，没被标记）
    • 标记：nums[3] = 7 + 8 = 15
      现在数组变成：[4,3,2,15,8,2,3,1]

  2. 第二个数字 num=3：

    • 计算位置：x = (3-1) % 8 = 2 % 8 = 2（对应索引 2）
    • 检查 nums[2] 的值：原本是 2（2 <= 8，没被标记）
    • 标记：nums[2] = 2 + 8 = 10
      现在数组变成：[4,3,10,15,8,2,3,1]

  3. 第三个数字 num=2：

    • 计算位置：x = (2-1) % 8 = 1 % 8 = 1（对应索引 1）
    • 检查 nums[1] 的值：原本是 3（3 <= 8，没被标记）
    • 标记：nums[1] = 3 + 8 = 11
      现在数组变成：[4,11,10,15,8,2,3,1]

  4. 第四个数字 num=7：

    • 计算位置：x = (7-1) % 8 = 6 % 8 = 6（对应索引 6）
    • 检查 nums[6] 的值：原本是 3（3 <= 8，没被标记）
    • 标记：nums[6] = 3 + 8 = 11
      现在数组变成：[4,11,10,15,8,2,11,1]

  5. 第五个数字 num=8：

    • 计算位置：x = (8-1) % 8 = 7 % 8 = 7（对应索引 7）
    • 检查 nums[7] 的值：原本是 1（1 <= 8，没被标记）
    • 标记：nums[7] = 1 + 8 = 9
      现在数组变成：[4,11,10,15,8,2,11,9]

  6. 第六个数字 num=2：

    • 计算位置：x = (2-1) % 8 = 1 % 8 = 1（对应索引 1）
    • 检查 nums[1] 的值：现在是 11（11 > 8，已经被标记过了）
    • 不做操作，数组保持不变

  7. 第七个数字 num=3：

    • 计算位置：x = (3-1) % 8 = 2 % 8 = 2（对应索引 2）
    • 检查 nums[2] 的值：现在是 10（10 > 8，已经被标记过了）
    • 不做操作，数组保持不变

  8. 第八个数字 num=1：

    • 计算位置：x = (1-1) % 8 = 0 % 8 = 0（对应索引 0）
    • 检查 nums[0] 的值：原本是 4（4 <= 8，没被标记）
    • 标记：nums[0] = 4 + 8 = 12
      现在数组变成：[12,11,10,15,8,2,11,9]
第二步：第二次遍历数组，收集消失的数字

java

运行

List<Integer> ret = new ArrayList<Integer>(); // 准备存放结果
for (int i = 0; i < n; i++) { // 遍历每个位置
    if (nums[i] <= n) { // 如果这个位置的数没被标记（没加过n）
        ret.add(i + 1); // 这个位置对应的数字就是消失的数字
    }
}
return ret;

遍历修改后的数组 [12,11,10,15,8,2,11,9]：

  • 索引 0：nums[0]=12（12 > 8 → 被标记过）→ 对应数字 1 出现过
  • 索引 1：nums[1]=11（11 > 8 → 被标记过）→ 对应数字 2 出现过
  • 索引 2：nums[2]=10（10 > 8 → 被标记过）→ 对应数字 3 出现过
  • 索引 3：nums[3]=15（15 > 8 → 被标记过）→ 对应数字 4 出现过
  • 索引 4：nums[4]=8（8 <= 8 → 没被标记过）→ 对应数字 5 消失了，加入结果
  • 索引 5：nums[5]=2（2 <= 8 → 没被标记过）→ 对应数字 6 消失了，加入结果
  • 索引 6：nums[6]=11（11 > 8 → 被标记过）→ 对应数字 7 出现过
  • 索引 7：nums[7]=9（9 > 8 → 被标记过）→ 对应数字 8 出现过

最终结果就是 [5,6]，和示例一致。

关键细节解释

  1. 为什么要用 (num - 1) % n？
    因为第一次遍历中，有些数字可能已经被 “加 n” 了（比如原本是 3，加 n 后变成 11），%n 能把它还原成原本的数字（11%8=3），保证计算的位置正确。

  2. 为什么 nums[x] <= n 就表示没被标记？
    原数组的数字最大是 n，一旦被标记（加 n），就会变成 >n，所以用 <=n 能准确判断是否被标记过。

  3. 为什么最后 i+1 是消失的数字？
    因为索引 i 对应的 “应该出现的数字” 是 i+1（比如索引 0 对应 1，索引 1 对应 2，…，索引 4 对应 5）。

这个方法的精髓就是 “利用数组自身空间做标记”，既不额外占内存，又能在 O (n) 时间内解决问题，非常巧妙～

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布