给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有
arr[2 * i + 1] = 2 * arr[2 * i]” 时，返回 true；否则，返回 false。
示例 1：
**输入：** arr = [3,1,3,6]
**输出：** false
示例 2：
**输入：** arr = [2,1,2,6]
**输出：** false
示例 3：
**输入：** arr = [4,-2,2,-4]
**输出：** true
**解释：** 可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]
提示：
0 <= arr.length <= 3 * 104arr.length 是偶数-105 <= arr[i] <= 105
方法一：哈希表 + 排序
设 arr 的长度为 n，题目本质上是问 arr 能否分成 \dfrac{n}{2 对元素，每对元素中一个数是另一个数的两倍。
设 cnt}[x] 表示 arr 中 x 的个数。
对于 arr 中的 0，它只能与 0 匹配。如果 cnt}[0] 是奇数，那么必然无法满足题目要求。
去掉 arr 中的 0。设 x 为 arr 中绝对值最小的元素，由于没有绝对值比 x 更小的数，因此 x 只能与 2x 匹配。如果此时 cnt}[2x] < \textit{cnt}[x]，那么会有部分 x 无法找到它的另一半，即无法满足题目要求；否则将所有 x 和 cnt}[x] 个 2x 从 arr 中去掉，继续判断剩余元素是否满足题目要求。不断重复此操作，如果某个时刻 arr 为空，则说明 arr 可以满足题目要求。
代码实现时，我们可以用一个哈希表来统计 cnt，并将其键值按绝对值从小到大排序，然后模拟上述操作，去掉元素的操作可以改为从 cnt 中减去对应值。
[sol1-Python3]1
2
3
4
5
6
7
8
9
10
| class Solution:
def canReorderDoubled(self, arr: List[int]) -> bool:
cnt = Counter(arr)
if cnt[0] % 2:
return False
for x in sorted(cnt, key=abs):
if cnt[2 * x] < cnt[x]:
return False
cnt[2 * x] -= cnt[x]
return True
|
[sol1-C++]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
| 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]) {
return false;
}
cnt[2 * x] -= cnt[x];
}
return true;
}
};
|
[sol1-Java]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
| class Solution {
public boolean canReorderDoubled(int[] arr) {
Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
for (int x : arr) {
cnt.put(x, cnt.getOrDefault(x, 0) + 1);
}
if (cnt.getOrDefault(0, 0) % 2 != 0) {
return false;
}
List<Integer> vals = new ArrayList<Integer>();
for (int x : cnt.keySet()) {
vals.add(x);
}
Collections.sort(vals, (a, b) -> Math.abs(a) - Math.abs(b));
for (int x : vals) {
if (cnt.getOrDefault(2 * x, 0) < cnt.get(x)) {
return false;
}
cnt.put(2 * x, cnt.getOrDefault(2 * x, 0) - cnt.get(x));
}
return true;
}
}
|
[sol1-C#]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
| public class Solution {
public bool CanReorderDoubled(int[] arr) {
Dictionary<int, int> cnt = new Dictionary<int, int>();
foreach (int x in arr) {
if (!cnt.ContainsKey(x)) {
cnt.Add(x, 1);
} else {
++cnt[x];
}
}
if (cnt.ContainsKey(0) && cnt[0] % 2 != 0) {
return false;
}
List<int> vals = new List<int>();
foreach (int x in cnt.Keys) {
vals.Add(x);
}
vals.Sort((a, b) => Math.Abs(a) - Math.Abs(b));
foreach (int x in vals) {
if ((cnt.ContainsKey(2 * x) ? cnt[2 * x] : 0) < cnt[x]) {
return false;
}
if (cnt.ContainsKey(2 * x)) {
cnt[2 * x] -= cnt[x];
} else {
cnt.Add(2 * x, -cnt[x]);
}
}
return true;
}
}
|
[sol1-Golang]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
| func canReorderDoubled(arr []int) bool {
cnt := make(map[int]int, len(arr))
for _, x := range arr {
cnt[x]++
}
if cnt[0]%2 == 1 {
return false
}
vals := make([]int, 0, len(cnt))
for x := range cnt {
vals = append(vals, x)
}
sort.Slice(vals, func(i, j int) bool { return abs(vals[i]) < abs(vals[j]) })
for _, x := range vals {
if cnt[2*x] < cnt[x] {
return false
}
cnt[2*x] -= cnt[x]
}
return true
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
|
[sol1-C]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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| typedef struct {
int key;
int val;
UT_hash_handle hh;
} HashItem;
static int cmp(const int * pa, const int * pb) {
return abs(*pa) - abs(*pb);
}
bool canReorderDoubled(int* arr, int arrSize){
HashItem * cnt = NULL;
HashItem * pEntry = NULL;
for (int i = 0; i < arrSize; i++) {
pEntry = NULL;
HASH_FIND_INT(cnt, &arr[i], pEntry);
if (NULL == pEntry) {
pEntry = (HashItem *)malloc(sizeof(HashItem));
pEntry->key = arr[i];
pEntry->val = 1;
HASH_ADD_INT(cnt, key, pEntry);
} else {
pEntry->val++;
}
}
pEntry = NULL;
int key = 0;
HASH_FIND_INT(cnt, &key, pEntry);
if (pEntry != NULL && pEntry->val % 2) {
return false;
}
int cntSize = HASH_COUNT(cnt);
int * vals = (int *)malloc(sizeof(int) * cntSize);
int pos = 0;
HashItem * tmp;
HASH_ITER(hh, cnt, pEntry, tmp) {
vals[pos++] = pEntry->key;
}
qsort(vals, cntSize, sizeof(int), cmp);
for (int i = 0; i < cntSize; i++) {
int c1 = 0, c2 = 0;
int key = vals[i];
HashItem * pEntry1 = NULL;
HashItem * pEntry2 = NULL;
HASH_FIND_INT(cnt, &key, pEntry1);
if (pEntry1) {
c1 = pEntry1->val;
}
key = 2 * vals[i];
HASH_FIND_INT(cnt, &key, pEntry2);
if (pEntry2) {
c2 = pEntry2->val;
}
if (c2 < c1) {
return false;
}
if (pEntry2) {
pEntry2->val -= c1;
}
}
HASH_ITER(hh, cnt, pEntry, tmp) {
HASH_DEL(cnt, pEntry);
free(pEntry);
}
free(vals);
return true;
}
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| var canReorderDoubled = function(arr) {
const cnt = new Map();
for (const x of arr) {
cnt.set(x, (cnt.get(x) || 0) + 1);
}
if ((cnt.get(0) || 0) % 2 !== 0) {
return false;
}
const vals = [];
for (const x of cnt.keys()) {
vals.push(x);
}
vals.sort((a, b) => Math.abs(a) - Math.abs(b));
for (const x of vals) {
if ((cnt.get(2 * x) || 0) < cnt.get(x)) {
return false;
}
cnt.set(2 * x, (cnt.get(2 * x) || 0) - cnt.get(x));
}
return true;
};
|
复杂度分析
