class Solution { public: bool canReorderDoubled(vector<int> &arr) { unordered_map<int, int> cnt; for (int x : arr) { ++cnt[x]; } if (cnt[0] % 2) { return false; } vector<int> vals; vals.reserve(cnt.size()); for (auto &[x, _] : cnt) { vals.push_back(x); } sort(vals.begin(), vals.end(), [](int a, int b) { return abs(a) < abs(b); }); for (int x : vals) { if (cnt[2 * x] < cnt[x]) { // 无法找到足够的 2x 与 x 配对 return false; } cnt[2 * x] -= cnt[x]; } return true; } };
时间: 2023-05-28 21:04:04 浏览: 125
A) {
unordered_map<int, int> freq; // to store frequency of each number
for(int num : A) freq[num]++;
vector<int> nums; // to store unique numbers in ascending order
for(auto p : freq) nums.push_back(p.first);
sort(nums.begin(), nums.end());
for(int num : nums) {
if(freq[num] == 0) continue; // if current number is already processed, skip it
int doubleNum = num * 2; // find the double of current number
if(doubleNum == 0) { // if current number is 0, it can only be paired with itself
if(freq[num] % 2 != 0) return false; // if frequency of current number is odd, return false
freq[num] = 0; // mark current number as processed
continue;
}
if(freq[num] > freq[doubleNum]) return false; // if frequency of current number is greater than frequency of its double, return false
freq[doubleNum] -= freq[num]; // subtract frequency of current number from frequency of its double
freq[num] = 0; // mark current number as processed
}
return true; // if all numbers are processed successfully, return true
}
};
阅读全文