JZX轻语：简

LeetCode 954 - 二倍数对数组

发表于2024年05月28日

#数组 #哈希表 #排序

类似于题目2007，使用贪心法从小到大处理数字。但该题涉及到负数，因此，排序的逻辑需要改为按绝对值递增处理。先使用哈希表cnt_map对数字计数。然后按绝对值从小到大遍历数字num，尝试抽取cnt_map[num]次组(num, num * 2)，如果数字num * 2的计数小于cnt_map[num]，则无法完成题目要求，直至所有的牌处理完毕。对于特殊情况num == 0，需要特殊处理，即判断cnt_map[0]是否为偶数。

class Solution:
    def canReorderDoubled(self, arr: List[int]) -> bool:
        cnt_map = {}
        for num in arr:
            cnt_map[num] = cnt_map.get(num, 0) + 1

        for num in sorted(cnt_map.keys(), key=lambda _item: abs(_item)):
            if num == 0:
                if cnt_map[0] % 2:
                    return False
                continue

            if cnt_map[num] == 0:
                continue
            double = num * 2
            if double not in cnt_map or cnt_map[double] < cnt_map[num]:
                return False
            cnt_map[double] -= cnt_map[num]
        return True

闪念标签：LC

题目链接：https://leetcode.cn/problems/array-of-doubled-pairs/