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:
0 <= A.length <= 30000 A.length is even -100000 <= A[i] <= 100000
[1,2,1,-8,8,-4,4,-4,2,-2] [0,0,0,0,0,0] [3,1,3,6] [2,1,2,6] [4,-2,2,-4,0,1] [4,-2,2,-4,0,0] [1,2,4,16,8,4]
// 120ms, 54%
class Solution {
public:
bool canReorderDoubled(vector<int>& A) {
const int N = 100001;
vector<int> buf1(N, 0), buf2(N, 0);
for (auto a : A) {
if (a >= 0) {
buf1[a]++;
} else {
buf2[-a]++;
}
}
int res = buf1[0]/2;
for (int i = 1; i <= N/2; i++) {
if (buf1[i] > 0 && buf1[2*i] > 0) {
int n = min(buf1[i], buf1[2*i]);
buf1[i] -= n;
buf1[2*i] -= n;
res += n;
}
if (buf2[i] > 0 && buf2[2*i] > 0) {
int n = min(buf2[i], buf2[2*i]);
buf2[i] -= n;
buf2[2*i] -= n;
res += n;
}
}
return res == A.size()/2;
}
};