442. 数组中重复的数据
1.题目描述
给定一个整数数组 a,其中1 ≤ a[i] ≤ n (n为数组长度), 其中有些元素出现两次而其他元素出现一次。
找到所有出现两次的元素。
你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗?
示例:
2.思路
利用题目中所给信息 1 ≤ a[i] ≤ n ,将出现过的数字作为数组的index(访问元素时需要减一),如果出现一次的,将该index下的数取相反数,记录此时的状态,如果值为index的数字再出现一次(此时index索引的值为负数),那么这个数字就出现了两次。
比如 数组 [2,2,1] , 第一次更新后 index = 2 索引的元素取相反数 [2,-2,1], 第二次更新 index = 2 , 此时数组元素已为负,所以2就是其中的一个结果。
3.代码
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> res;
if(nums.empty()){
return res;
}
for(auto& n : nums){
int index = abs(n);
if(nums[index - 1] < 0){
res.push_back(index);
}
else{
nums[index - 1] = -nums[index - 1];
}
}
return res;
}
};
4.复杂度分析
时间复杂度:O(n)
空间复杂度:O(1)