题目要求使用 O(1)的空间复杂度和 O(n)的时间复杂度来解决问题，所以不能使用排序或者 map 的方法。
因为数组中的数字是从 1 到 n 的，这就让我想起了Set Mismatch 中的解法，先将数组尽量摆放在合适的位置上（数字 i 对应数组中的位置 i-1），然后在统计一遍不在合适位置上的数字即可。
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> result;
for(int i=0;i<nums.size();i++){
while(nums[i]!=i+1 && nums[nums[i]-1]!=nums[i]){
int j=nums[i]-1;
int t=nums[i];
nums[i]=nums[j];
nums[j]=t;
}
}
for(int i=0;i<nums.size();i++){
if(nums[i]!=i+1) result.push_back(nums[i]);
}
return result;
}
};
|
接着，在 solution 中看见了更简单的方法，因为数组中的所有数字都是正数，所以可以在数组中将某位置原数字变为负数来表示该位置中的数字已经出现过。具体过程：第一次遇到某个数字的时候将对应位置的数字变成其相反数，然后在某一次如果遇到某一数字对应位置是负数的话，说明之前出现过该数字，则将该数字加入返回值的列表中。
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> result;
for(int i=0;i<nums.size();i++){
int j=abs(nums[i])-1;
if(nums[j]<0) result.push_back(j+1);
else nums[j]*=-1;
}
return result;
}
};
|