发表于 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 题目链接