0448. Find All Numbers Disappeared in an Array ============================================== 题目信息 -------- :题号: 0448 :难度: Easy :主题: 长度为 ``n`` 的数组、数值范围 ``1..n``、缺失整数、结果集合 :原题: `LeetCode 0448 `_ :重点: 找出完整范围中未出现的值、重复元素不会重复占范围位置、结果顺序不限、允许修改输入 题目重述 -------- 给定长度为 ``n`` 的整数数组 ``nums``,其中每个元素都位于 ``[1, n]``。返回范围 ``1..n`` 中所有没有在数组中出现的整数。 ``n`` 位于 ``[1, 10^5]``。输入可能包含重复值,因此会有同样数量的范围值缺失。每个缺失整数在结果中只出现一次,结果顺序不限。题目要求使用 ``O(n)`` 时间,并且除返回数组外不使用额外空间;允许原地修改 ``nums``。 自建示例 -------- 两个重复值对应两个缺失值: .. code-block:: text 输入:nums = [1, 1, 2, 4, 6, 6] 输出:[3,5] 解释:数组长度为 6,完整范围是 1..6;其中 3 和 5 从未出现。 所有范围值都出现: .. code-block:: text 输入:nums = [2, 1] 输出:[] 解释:范围 1..2 中的两个整数都至少出现一次,因此没有缺失值。 用出现值标记对应范围位置 ------------------------ 值 ``x`` 对应下标 ``x - 1``。第一次看到 ``x`` 时,将 ``nums[x - 1]`` 变为负数,表示范围值 ``x`` 出现过;完成标记后再次扫描,仍为正数的下标 ``i`` 就代表值 ``i + 1`` 从未出现。 读取输入值时先取绝对值,因为数组中的元素可能已经被前面的标记取反。重复值只会重复访问同一位置,不会影响“是否出现”的最终状态。 C++ 实现 -------- .. code-block:: cpp class Solution { public: std::vector findDisappearedNumbers(std::vector& nums) { for (int value : nums) { int index = std::abs(value) - 1; if (nums[index] > 0) nums[index] = -nums[index]; } std::vector result; for (int i = 0; i < static_cast(nums.size()); ++i) { if (nums[i] > 0) result.push_back(i + 1); } return result; } }; 代码分析 -------- 原数组的每个槽位同时承担“对应值是否出现”的标记位,第二次扫描将正槽位反解为缺失值。取绝对值保证已被改写的元素仍能正确映射下标;标记和收集各扫描一次,时间复杂度为 ``O(n)``,除返回结果外额外空间复杂度为 ``O(1)``。