class Solution {
public:
bool canReorderDoubled(vector<int>& arr) {
}
};
954. 二倍数对数组
给定一个长度为偶数的整数数组 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原站题解
javascript 解法, 执行用时: 96 ms, 内存消耗: 47.9 MB, 提交时间: 2023-03-09 15:30:04
/**
* @param {number[]} arr
* @return {boolean}
*/
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)) { // 无法找到足够的 2x 与 x 配对
return false;
}
cnt.set(2 * x, (cnt.get(2 * x) || 0) - cnt.get(x));
}
return true;
};
golang 解法, 执行用时: 88 ms, 内存消耗: 9.3 MB, 提交时间: 2023-03-09 15:29:24
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] { // 无法找到足够的 2x 与 x 配对
return false
}
cnt[2*x] -= cnt[x]
}
return true
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
java 解法, 执行用时: 22 ms, 内存消耗: 48.6 MB, 提交时间: 2023-03-09 15:28:26
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)) { // 无法找到足够的 2x 与 x 配对
return false;
}
cnt.put(2 * x, cnt.getOrDefault(2 * x, 0) - cnt.get(x));
}
return true;
}
}
python3 解法, 执行用时: 72 ms, 内存消耗: 16.9 MB, 提交时间: 2023-03-09 15:28:07
'''
数组分成
'''
class Solution:
def canReorderDoubled(self, arr: List[int]) -> bool:
cnt = Counter(arr)
if cnt[0] % 2: # 0有奇数个，则无法配对
return False
for x in sorted(cnt, key=abs):
if cnt[2 * x] < cnt[x]: # 无法找到足够的 2x 与 x 配对
return False
cnt[2 * x] -= cnt[x]
return True