0442. Find All Duplicates in an Array
=====================================
题目信息
--------
:题号: 0442
:难度: Medium
:主题: 长度为 ``n`` 的数组、数值范围 ``1..n``、出现两次、重复值集合
:原题: `LeetCode 0442 `_
:重点: 每个值只出现一次或两次、结果只列出现两次的值、顺序不限、要求线性时间和常数额外空间
题目重述
--------
给定长度为 ``n`` 的整数数组 ``nums``,每个元素都位于 ``[1, n]``,并且每个整数在数组中出现一次或两次。返回所有恰好出现两次的整数。
``n`` 位于 ``[1, 10^5]``。每个重复值在结果中只出现一次,结果顺序不限。题目要求使用 ``O(n)`` 时间,并且除返回结果外只使用常数额外空间;允许在处理过程中修改输入数组。
自建示例
--------
存在两个重复值:
.. code-block:: text
输入:nums = [1, 3, 4, 2, 2, 3]
输出:[2,3]
解释:2 和 3 各出现两次,1 和 4 各出现一次;输出顺序也可以是 [3,2]。
没有重复值:
.. code-block:: text
输入:nums = [1, 2, 3]
输出:[]
解释:每个数都只出现一次,因此结果为空。
用下标位置记录出现次数
------------------------
数组值 ``x`` 的合法范围正好对应下标 ``x - 1``。第一次遇到 ``x`` 时,把 ``nums[x - 1]`` 取负作为“已经见过”的标记;再次遇到 ``x`` 时,该位置已经是负数,于是把 ``x`` 加入答案。读取值时先取绝对值,因为此前的标记可能已经改变了它的符号。
这种做法利用了题目允许修改输入数组的条件,不需要额外的布尔数组或哈希集合。由于每个值最多出现两次,每个负号只表示对应值已经被处理过,不会把同一个重复值加入多次。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
std::vector findDuplicates(std::vector& nums) {
std::vector result;
for (int value : nums) {
int index = std::abs(value) - 1;
if (nums[index] < 0) {
result.push_back(index + 1);
} else {
nums[index] = -nums[index];
}
}
return result;
}
};
代码分析
--------
值与下标的一一映射把“是否出现过”编码进原数组:第一次访问对应位置时变负,第二次访问时检测到负号。遍历过程中始终对当前值取绝对值,因此前面被标记的元素仍能作为后续输入使用。每个元素只处理一次,时间复杂度为 ``O(n)``,除返回结果外额外空间复杂度为 ``O(1)``。