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

约 4 分钟
文章信息 8 个分类 2 个标签
分类
LeetCode CodeTop 简单 已解决 2-5 字节 网易 猿辅导
标签
数组 哈希表

题目描述

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

image-20260928224431047

题意分析

数组长度为 n，每个数都在 1..n 中，找出这个范围内所有没有出现的值。数组可能重复，同一个值出现多少次不影响是否缺失；返回缺失数值，不是缺失位置的下标。

进阶要求线性时间、常数额外空间，返回结果不计入额外空间。当前解法借用输入数组的符号记录出现状态，会修改数组，但不会丢失各位置原值的绝对值。

解法：利用下标原地标记出现过的数字

核心思路

[!blue]

值域正好有 n 个可能值，可以给每个值指定一个标记位置：值 v 对应下标 v - 1。若使用额外布尔数组就能记录是否出现，而本题输入全为正数，原数组的符号也可以承担这个标记。

遍历到原值 v 时，将 nums[v - 1] 设为负数，表示值 v 已出现。这里只改变正负号，不改变大小，因此被标记位置之后轮到作为输入读取时，可以用绝对值恢复它原来保存的数值，再继续为这个原值设置标记。

同一个值可能出现多次，标记操作必须幂等：目标位置已经为负就不再变化，只在仍为正时取负。不能每次都翻转，否则重复出现会把“见过”状态擦掉。

第一遍完成后，下标 i 为负当且仅当原数组出现过值 i + 1。所以第二遍只需收集仍为正的位置对应的 i + 1。必须等全部标记结束再收集，因为尚未扫描的后面仍可能出现某个值。

解题步骤

  1. 遍历输入，先对当前位置取绝对值，得到原值 v。
  2. 映射到下标 v - 1，若该位置为正就取负，已经为负则保持。
  3. 第一遍完成后重新扫描数组，将每个正数位置对应的 i + 1 加入答案。
  4. 返回结果，负号标记会保留在输入数组中。

代码实现

class Solution {
    // 可以把原数组当成访问标记表：看到值 value 时，将 nums[value - 1] 置为负数。
    public List<Integer> findDisappearedNumbers(int[] nums) {
        for (int num : nums) {
            // 当前位置可能已经取负，先恢复原值再映射下标
            int idx = Math.abs(num) - 1;

            // 重复值只保留负标记，不将它再次翻回正数
            if (nums[idx] > 0) {
                nums[idx] = -nums[idx];
            }
        }

        List<Integer> res = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                res.add(i + 1);
            }
        }

        return res;
    }
}

func findDisappearedNumbers(nums []int) []int {
    // 可以把原数组当成访问标记表：看到值 value 时，将 nums[value - 1] 置为负数。
    for i := 0; i < len(nums); i++ {
        // 当前位置可能已经取负，先恢复原值再映射下标
        idx := nums[i]
        if idx < 0 {
            idx = -idx
        }
        idx--
        // 重复值只保留负标记，不将它再次翻回正数
        if nums[idx] > 0 {
            nums[idx] = -nums[idx]
        }
    }

    res := make([]int, 0)
    for i, val := range nums {
        if val > 0 {
            res = append(res, i+1)
        }
    }

    return res
}

复杂度分析

  • 时间复杂度：$O(n)$，两次线性扫描。
  • 空间复杂度：$O(1)$，借用输入符号记录状态，结果列表另计。

关键点总结

[!green]

  • 当前元素的绝对值用来继续读取原输入，当前下标的符号用来表示对应值是否出现，二者不是同一层含义。
  • 值域 1..n 保证映射合法，原值全正保证正负号可以区分状态。
  • 同一标记只从正变负，不因重复值再次翻回。
  • 返回数值 i + 1，而不是存放标记的零基下标。

易错点总结

[!yellow]

  • 读取已被标记的输入时不取绝对值，会用负数计算非法下标。
  • 每次遇到重复值都翻转符号，会让偶数次出现的值错误地变成未出现。
  • 标记尚未全部完成就收集答案，可能把后面将出现的值误报为缺失。
  • 映射时忘记减一或输出时忘记加一，会混淆值域与数组下标。
  • 本实现会修改输入，不能把它描述为只读扫描。

相似题目

题目 难度 关联与区别
442. 数组中重复的数据 中等 出现标记相同，原题在重复命中时收集值，本题在标记结束后找未出现位置。
41. 缺失的第一个正数 困难 本题值域已在1到n，原题还需忽略非正数和超范围值，再寻找最小缺失正数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/26730924
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！