0442. Find All Duplicates in an Array¶
题目信息¶
- 题号:
0442
- 难度:
Medium
- 主题:
长度为
n的数组、数值范围1..n、出现两次、重复值集合- 原题:
- 重点:
每个值只出现一次或两次、结果只列出现两次的值、顺序不限、要求线性时间和常数额外空间
题目重述¶
给定长度为 n 的整数数组 nums,每个元素都位于 [1, n],并且每个整数在数组中出现一次或两次。返回所有恰好出现两次的整数。
n 位于 [1, 10^5]。每个重复值在结果中只出现一次,结果顺序不限。题目要求使用 O(n) 时间,并且除返回结果外只使用常数额外空间;允许在处理过程中修改输入数组。
自建示例¶
存在两个重复值:
输入:nums = [1, 3, 4, 2, 2, 3]
输出:[2,3]
解释:2 和 3 各出现两次,1 和 4 各出现一次;输出顺序也可以是 [3,2]。
没有重复值:
输入:nums = [1, 2, 3]
输出:[]
解释:每个数都只出现一次,因此结果为空。
用下标位置记录出现次数¶
数组值 x 的合法范围正好对应下标 x - 1。第一次遇到 x 时,把 nums[x - 1] 取负作为“已经见过”的标记;再次遇到 x 时,该位置已经是负数,于是把 x 加入答案。读取值时先取绝对值,因为此前的标记可能已经改变了它的符号。
这种做法利用了题目允许修改输入数组的条件,不需要额外的布尔数组或哈希集合。由于每个值最多出现两次,每个负号只表示对应值已经被处理过,不会把同一个重复值加入多次。
C++ 实现¶
class Solution {
public:
std::vector<int> findDuplicates(std::vector<int>& nums) {
std::vector<int> 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)。