难度: Medium
给定一个长度为偶数的整数数组 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运行时间: 56 ms
内存: 18.1 MB
class Solution:
def canReorderDoubled(self, arr: List[int]) -> bool:
cnt = Counter(arr)
if cnt[0] % 2:
return False
# arr = sorted(cnt, key=abs)
# print(arr, cnt)
for x in sorted(cnt, key=abs):
if cnt[2 * x] < cnt[x]:
return False
cnt[2 * x] -= cnt[x]
return True
此题解首先利用Counter统计数组中每个元素的出现次数。针对0特殊处理，因为0的两倍还是0，如果0的个数为奇数，则无法成对，直接返回false。接着对元素按绝对值从小到大排序，这是为了保证处理较小元素时，其两倍元素也已经在哈希表中。对于每个元素x，检查其两倍的元素2*x在哈希表中的计数是否不少于x的计数。如果少于，则返回false，因为无法为每个x找到对应的2*x。如果计数足够，则将2*x的计数减去x的计数，表示这部分配对已经完成。如果所有元素都能成功配对，则返回true。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def canReorderDoubled(self, arr: List[int]) -> bool:
cnt = Counter(arr) # 统计数组中每个元素的出现次数
if cnt[0] % 2:
return False # 如果0的个数为奇数，直接返回false
# 对元素按绝对值大小排序，确保先处理小的元素
for x in sorted(cnt, key=abs):
if cnt[2 * x] < cnt[x]:
return False # 如果两倍数的计数小于当前数的计数，无法配对成功
cnt[2 * x] -= cnt[x] # 减少两倍数的计数，表示配对
return True # 所有元素都能配对成功
将数组元素按照绝对值排序是为了确保在处理每个元素x时，其对应的两倍数2*x也已经在可考虑的范围内。这种排序方式可以避免在查找配对时出现先遇到大数后遇到对应小数的情况，从而确保每次处理元素时，其两倍的元素也已被考虑。这样做可以有效地配对，避免处理顺序导致的错误判断。
如果某个元素x的两倍2*x不存在于数组中，或者其数量不足以与x完全配对，算法将返回false。在算法中，会检查哈希表中2*x的计数是否不少于x的计数，如果少于x的计数，则无法为每个x找到足够的2*x进行配对，因此算法将判断无法成功配对所有元素，并返回false。
在算法中，对0元素的特殊处理是检查其数量是否为偶数。因为0的两倍仍然是0，所以每个0都必须与另一个0配对。如果0的数量是奇数，则至少有一个0无法找到配对，因此算法直接返回false。只有当0的数量是偶数时，这些0才能完全按对配对成功。
在算法的实现中，如果减少两倍数2*x的计数后计数变为负数，这表明在之前的步骤中，2*x的数量已经不足以与x配对。然而，算法设计应避免此类情况，因为在减少计数之前，算法已经检查了2*x的计数是否足够。如果实际操作中发生了负数情况，这可能指出程序的逻辑错误或数据处理错误。正常情况下，算法确保在减少计数前，2*x的数量总是足够的，不会产生负数。