# 954. Array of Doubled Pairs

Given an array of integers `A` with even length, return `true` if and only if it is possible to reorder it such that `A[2 * i + 1] = 2 * A[2 * i]` for every `0 <= i < len(A) / 2`.

Example 1:

``````Input: [3,1,3,6]
Output: false
``````

Example 2:

``````Input: [2,1,2,6]
Output: false
``````

Example 3:

``````Input: [4,-2,2,-4]
Output: true
Explanation: We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].
``````

Example 4:

``````Input: [1,2,4,16,8,4]
Output: false
``````

Note:

1. `0 <= A.length <= 30000`
2. `A.length` is even
3. `-100000 <= A[i] <= 100000`

``````class Solution {
public:
bool canReorderDoubled(vector<int>& A) {
unordered_map<int, int> m;
for (int num : A) ++m[num];
vector<int> keys;
for (auto &a : m) keys.push_back(a.first);
sort(keys.begin(), keys.end(), [](int i, int j) {return abs(i) < abs(j);});
for (int key : keys) {
if (m[key] > m[2 * key]) return false;
m[2 * key] -= m[key];
}
return true;
}
};
``````

``````class Solution {
public:
bool canReorderDoubled(vector<int>& A) {
map<int, int> m;
for (int num : A) ++m[num];
for (auto &a : m) {
if (a.second == 0) continue;
int want = a.first < 0 ? a.first / 2 : a.first * 2;
if ((a.first < 0 && a.first % 2 != 0) || a.second > m[want]) return false;
m[want] -= a.second;
}
return true;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/954

https://leetcode.com/problems/array-of-doubled-pairs/

https://leetcode.com/problems/array-of-doubled-pairs/discuss/209564/Java-Heap-Concise

https://leetcode.com/problems/array-of-doubled-pairs/discuss/203183/JavaC%2B%2BPython-Match-from-the-Smallest-or-Biggest-100

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation