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?
Example:
Input:
[4,3,2,7,8,2,3,1]
Output:
[2,3]
思路:先将数组排序,然后判断是否重复,即若nums[i] != nums[i+1],即说明nums[i]非重复元素,可以删去.
重点在于指针(迭代器)的操作,由于vector的erase(删除)操作需要通过迭代器进行,而且删除元素后,右侧的元素全部左移一格,这就导致一开始写的时候总是找不到bug所在.
例如排序后的
1 2 2 3 3 4 5 6 7 8
得到却是
2 3 4 6 8
为何非重复的4,6都没删呢?就是因为erase第二个3之后,it实际上已经指向4,此时再it++,就指向5了.同理6也这样被跳过.
此外还有最后一位元素,若是重复的,直接pop掉即可,若是非重复的,也可以pop掉,所以it只遍历到end-1,最后整个数组pop_back()即可.
vector<int> findDuplicates(vector<int>& nums) {
sort(nums.begin(), nums.end()); //先排序
vector<int>::iterator it = nums.begin();
while (it != nums.end()-1) {
if (*it != *(it+1)) nums.erase(it); //找到则删除
else it++; //找不到则指针后移
}
nums.pop_back();
return nums;
}
思路2(借鉴别人的,非常巧妙):
由于数字范围与数组长度有关(1 ≤ a[i] ≤ n ),因此可以将元素值与元素下标联系起来(由于下标范围是0~n-1,因此还需要做一个偏移).从头遍历数组nums,将元素值作为下标(index)访问数组相应位置,然后置为相反数,若这个位置nums[index]被访问过,则<0,这样就知道重复了两次.
vector<int> findDuplicates(vector<int>& nums) {
vector<int> res;
for (int i = 0; i < nums.size(); i++) {
int index = abs(nums[i]) - 1; // 数组元素值映射为下标
if (nums[index] < 0) { // 若<0,说明之前访问过,这是第二次访问
res.push_back(index+1); // 这个位置符合
}
nums[index] = -nums[index]; // 置为相反数
}
return res;
}
