难度：Medium
使用最后的结果数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
int sz = nums.size();
vector<int> ret(sz+1,0);
for(int i = 0; i < nums.size(); i++)
{
ret[nums[i]]++;
}
for(int i = 0; i <= sz; i++)
{
if(ret[i] == 2)
ret.push_back(i);
}
ret.erase(ret.begin(),ret.begin()+sz+1);
return ret;
}
};
|
142ms,93.06%
遍历数组，如果nums[i]与i+1相等，则continue；如果不相等，则tmp = nums[i]，tmp－1为nums[i]应该在的位置，如果nums[i]与nums[tmp-1]不相等，交换nums[i]与nums[tmp-1]的元素，此时不要记录重复元素，会有重复的情况。交换完元素之后，遍历数组求解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> ret;
for(int i = 0; i < nums.size();i++)
{
if(nums[i] != i+1)
{
int temp = nums[i];
if(nums[i] != nums[temp-1])
{
nums[i] = nums[temp-1];
nums[temp-1] = temp;
i--;
}
}
}
for(int i = 0; i < nums.size();i++)
{
if(nums[i] != i+1)
ret.push_back(nums[i]);
}
return ret;
}
};
|
192ms,28.85%
用额外空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int>temp(nums.size(),0);
vector<int>ret;
for(int i = 0;i < nums.size();i++)
{
int cur = nums[i];
temp[cur-1]++;
}
for(int i = 0;i < nums.size(); i++)
{
if(temp[i] == 2)
ret.push_back(i+1);
}
return ret;
}
};
|
149ms，73.67％
近期评论