来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/array-of-doubled-pairs
题目
给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i + 1] = 2 * arr[2 * i]” 时，返回 true；否则，返回 false。
思路
负数和负数配对，正数和正数配对，剩下的偶数个0。将正负数分开并排序后判断，对于出现k次的数j，2*j出现次数小于等于k时无法配对。用个map记录出现的次数顺便排序，其中负数使用greater<int>从大到小排序。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| class Solution {
public:
bool canReorderDoubled(vector<int>& arr) {
int n = arr.size();
map<int,int,greater<int>> neg;
map<int,int> pos;
int zeros = 0;
for (int i = 0 ; i < n ; ++i) {
if (arr[i] > 0) {
pos[arr[i]]++;
} else if (arr[i] < 0) {
neg[arr[i]]++;
} else {
++zeros;
}
}
if (zeros&1) {
return false;
}
for (auto &it:pos) {
int j = it.first;
int k = it.second;
if (k == 0) {
continue;
}
if (pos.find(j*2) == pos.end() || pos[2*j] < k) {
return false;
}
pos[j] -= k;
pos[2*j] -= k;
}
for (auto &it:neg) {
int j = it.first;
int k = it.second;
if (k == 0) {
continue;
}
if (neg.find(j*2) == neg.end() || neg[2*j] < k) {
return false;
}
neg[j] -= k;
neg[2*j] -= k;
}
return true;
}
}
;
|