题目描述
Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Could you do it without extra space and in O(n) runtime?
例子
Input: [4,3,2,7,8,2,3,1] Output: [2,3]
解题思路
方法一
首先可以观察到题目讲明了数组中的元素都在长度范围内，而且要在线性时间和常数空间内解决，基本就排除了排序和哈希表的做法。我一开始的思路是利用数组元素作为下标，通过不停交换元素，相当于把元素放在它“正确”的下标中，例如 nums[3] = 2 就是正确的位置（因为元素值是从 1 到 n）。如果遇到要交换的位置已经是正确的元素就意味出现了重复。代码如下：
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> duplicates;
int index = 0;
while (index < nums.size()) {
while (nums[index] != index + 1 && nums[index] != 0) {
int correct_index = nums[index] - 1;
if (nums[correct_index] == correct_index + 1) {
duplicates.push_back(nums[correct_index]);
nums[index] = 0;
break;
}
swap(nums[index], nums[correct_index]);
}
index++;
}
return duplicates;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(1)
方法二
这是看 Discussion 里的方法，同样也是通过元素找到正确下标，但是不交换元素，而是直接将对应位置的数值变成负值，表示该下标对应的数值已经出现过了，这样当第二次遇到的时候就可以直接判断了，思路更加清晰，代码如下：
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> duplicates;
for (int i = 0; i < nums.size(); i++) {
int index = abs(nums[i]);
if (nums[index - 1] > 0) {
nums[index - 1] = -nums[index - 1];
} else {
duplicates.push_back(index);
}
}
return duplicates;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(1)