题目描述
给定一个长度为偶数的整数数组 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 * 104
arr.length
是偶数
-105 <= arr[i] <= 105
解法
方法一:哈希表 + 排序
| class Solution:
def canReorderDoubled(self, arr: List[int]) -> bool:
freq = Counter(arr)
if freq[0] & 1:
return False
for x in sorted(freq, key=abs):
if freq[x << 1] < freq[x]:
return False
freq[x << 1] -= freq[x]
return True
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | class Solution {
public boolean canReorderDoubled(int[] arr) {
Map<Integer, Integer> freq = new HashMap<>();
for (int v : arr) {
freq.put(v, freq.getOrDefault(v, 0) + 1);
}
if ((freq.getOrDefault(0, 0) & 1) != 0) {
return false;
}
List<Integer> keys = new ArrayList<>(freq.keySet());
keys.sort(Comparator.comparingInt(Math::abs));
for (int k : keys) {
if (freq.getOrDefault(k << 1, 0) < freq.get(k)) {
return false;
}
freq.put(k << 1, freq.getOrDefault(k << 1, 0) - freq.get(k));
}
return true;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution {
public:
bool canReorderDoubled(vector<int>& arr) {
unordered_map<int, int> freq;
for (int& v : arr) ++freq[v];
if (freq[0] & 1) return false;
vector<int> keys;
for (auto& [k, _] : freq) keys.push_back(k);
sort(keys.begin(), keys.end(), [](int a, int b) { return abs(a) < abs(b); });
for (int& k : keys) {
if (freq[k * 2] < freq[k]) return false;
freq[k * 2] -= freq[k];
}
return true;
}
};
|
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 {
freq := make(map[int]int)
for _, v := range arr {
freq[v]++
}
if freq[0]%2 != 0 {
return false
}
var keys []int
for k := range freq {
keys = append(keys, k)
}
sort.Slice(keys, func(i, j int) bool {
return abs(keys[i]) < abs(keys[j])
})
for _, k := range keys {
if freq[k*2] < freq[k] {
return false
}
freq[k*2] -= freq[k]
}
return true
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
|