发表于 2024.04.18

• 数组题，朴素的想法是遍历数组，对于数字i寻找是否有i // 2或者i * 2，但这样子如果都存在上述两种可能，则无法确定用哪个（如果用i // 2，则可能会存在i // 2 // 2找不到匹配的情况，而这个数是用来匹配i * 2的）。因此，需要使用贪心的办法，从小到大寻找双倍匹配，如果其中有个数无法找到双倍匹配，则直接返回空数组。

  有两种做法：一种基于哈希表，另一种则基于双指针查找。

  哈希表版本，需要特殊处理值为0的情况：

  class Solution:
      def findOriginalArray(self, changed: List[int]) -> List[int]:
          if len(changed) % 2:
              return []
  
          cnt = {}
          for num in changed:
              cnt[num] = cnt.get(num, 0) + 1
          ans = []
  
          # 从小到大寻找匹配
          # 小的数字要全部用完
          for num in sorted(cnt.keys()):
              if cnt[num] == 0:  # 已经用完了
                  continue
              c = cnt[num]  # 该数字的计数
              if num == 0:
                  c //= 2
              if cnt.get(2 * num, 0) < c:  # 双倍数不够用了
                  return []
              cnt[2 * num] -= c  # 使用掉对应数量的双倍数
              ans += [num] * c
          return ans

  使用双指针的方法，使用一个visited数组标记这个数字是否被使用了，指针i用于指向原来的数，j用于指向二倍数：

  class Solution:
      def findOriginalArray(self, changed: List[int]) -> List[int]:
          if len(changed) % 2:
              return []
  
          changed.sort()
          visited = [False] * len(changed)
          i, j = 0, 1
          result = []
          while i < len(changed):
              if not visited[i]:
                  visited[i] = True
  
                  double = changed[i] * 2
                  while j < len(changed):
                      # 找到第一个大于等于double、未被访问的数字
                      if not visited[j] and changed[j] >= double:
                          break
                      j += 1
                  # 找不到相应的匹配, 返回空数组
                  if j == len(changed) or changed[j] > double:
                      return []
  
                  visited[j] = True
                  result.append(changed[i])
              i += 1
          return result

• LC 题目链接