题目来源
找出数组中所有重复元素,我用了哈希的思想,但是用数组本身来记录,代码如下:
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
int i = 0, n = nums.size();
while (i < n) {
while (nums[i] != i+1 && nums[nums[i]-1] != nums[i])
iter_swap(nums.begin()+i, nums.begin()+nums[i]-1);
i++;
}
vector<int> res;
for (int j=0; j<n; j++) {
if (nums[j] != j+1)
res.push_back(nums[j]);
}
return res;
}
};
可以AC,不过其实还是用了额外的空间,时间复杂度应该是O(n)的呀,但是不知道为啥跑的那么慢。
看了大神们的做法,从前往后遍历一遍,把nums[i]对应位置的数变为负数,假如已经是负数了,说明重复了,push进去。
这种做法可以很方便的获得原nums,只要取下绝对值就可以。
代码如下:
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
int n = nums.size();
vector<int> res;
for (int i=0; i<n; i++) {
int index = abs(nums[i]) - 1;
if (nums[index] < 0)
res.push_back(index+1);
else
nums[index] = -nums[index];
}
return res;
}
};
网友评论