Python：从双倍列表中还原原列表

点击上方蓝字关注我们

题目描述

一个整数数组 original
可以通过每个元素值乘以 2 并随机打乱顺序，转变成一个新的数组 changed
。给定一个数组 changed
，任务是判断是否存在一个数组 original
使得 changed
是其对应的双倍数组。如果存在，返回可能的 original
数组；如果不存在，返回空数组。original
数组的元素可以以任意顺序返回。

示例

1. 输入： changed = [1,3,4,2,6,8]
   
   输出： [1,3,4]
   
   解释： 一个可能的 original
   数组为 [1,3,4]
   :

• 1 x 2 = 2
• 3 x 2 = 6
• 4 x 2 = 8
  其他可能的方案包括 [4,3,1]
  或 [3,1,4]
  。

2. 输入： changed = [6,3,0,1]
   
   输出： []
   
   解释： changed
   不是一个双倍数组。

3. 输入： changed = [1]
   
   输出： []
   
   解释： changed
   不是一个双倍数组。

提示

• 1 <= changed.length <= 105
  
• 0 <= changed[i] <= 105
  

解题思路

首先排序 changed
数组，以便从最小值开始匹配原数组 original
的元素与其双倍值。利用哈希表（计数器）来追踪各元素的剩余数量，从而验证是否每个元素的两倍都存在。如果无法为某个元素找到对应的双倍值，或者元素用尽，则判断 changed
不是双倍数组。

解析

class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        changed.sort()  # 对数组进行排序
        count = Counter(changed)  # 统计每个数字出现的次数
        res = []  # 初始化结果数组，用于存放原始数组
        for a in changed:  # 遍历数组中的每个元素
            if count[a] == 0:  # 如果当前元素的计数为0（已被使用完），则跳过
                continue
            count[a] -= 1  # 将当前元素的计数减1，表示使用一个
            if count[a * 2] == 0:  # 如果当前元素的两倍没有出现或已被使用完，则无法配对，返回空数组
                return []
            count[a * 2] -= 1  # 将当前元素两倍的计数减1，表示配对成功
            res.append(a)  # 将当前元素加入结果数组，作为原始数组的一部分
        return res  # 返回结果数组，即找到的原始数组

该算法的核心思想是首先对数组进行排序，便于从小到大配对元素与其翻倍的结果。使用一个计数器来跟踪每个元素的使用情况。对于数组中的每个元素，尝试找到其翻倍的对应元素，并相应地调整计数器。如果某个元素找不到合适的配对项，说明无法构成所需的翻倍数组，返回空数组。

性能考虑：

• 时间复杂度：O(N log N) 主要由排序步骤决定。
• 空间复杂度：O(N) 用于存储计数器和结果数组。

此方法有效处理了元素配对的问题，并确保所有元素都可以按要求翻倍匹配，适用于解决类似问题的场景。