文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
Find All Duplicates in an Array
2. Solution
- O(n), O(n)
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> result;
if(0 == nums.size()) {
return result;
}
int flag[nums.size()] = {0};
for(int i = 0; i < nums.size(); i++) {
if(flag[nums[i]]) {
result.push_back(nums[i]);
}
else {
flag[nums[i]] = 1;
}
}
return result;
}
};
- O(n), O(1)
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> result;
if(0 == nums.size()) {
return result;
}
for(int i = 0; i < nums.size(); i++) {
int index = abs(nums[i]) - 1;
if(nums[index] < 0) {
result.push_back(abs(nums[i]));
}
nums[index] = - nums[index];
}
return result;
}
};
