https://leetcode.com/problems/find-all-duplicates-in-an-array/#/description
像这种数组元素大小能够被bound且和数组size扯上关系,要条件反射想到类似bucket的做法。
类似的题:
leetcode 41 first missing positive
leetcode 287 find the duplicate number
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
if (nums.empty()) {
return vector<int>();
}
vector<int> ret;
for (int i = 0; i < nums.size(); ++i) {
int true_pos = nums[i] - 1;
if (nums[i] != i+1 && nums[i] != 0) {
if (nums[i] == nums[true_pos]) {
ret.push_back(nums[i]);
nums[i] = 0;
} else {
std::swap(nums[i], nums[true_pos]);
i--;
}
}
}
return ret;
}
};