从双倍数组中还原原数组

难度: Medium

一个整数数组 original 可以转变成一个双倍数组 changed ，转变方式为将 original 中每个元素 值乘以 2 加入数组中，然后将所有元素 随机打乱 。

给你一个数组 changed ，如果 change 是双倍数组，那么请你返回 original数组，否则请返回空数组。original 的元素可以以任意顺序返回。

示例 1：

输入：changed = [1,3,4,2,6,8]
输出：[1,3,4]
解释：一个可能的 original 数组为 [1,3,4] :
- 将 1 乘以 2 ，得到 1 * 2 = 2 。
- 将 3 乘以 2 ，得到 3 * 2 = 6 。
- 将 4 乘以 2 ，得到 4 * 2 = 8 。
其他可能的原数组方案为 [4,3,1] 或者 [3,1,4] 。

示例 2：

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

示例 3：

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

提示：

1 <= changed.length <= 10⁵
0 <= changed[i] <= 10⁵

Submission

运行时间: 103 ms

内存: 32.5 MB

class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        mx = max(changed)
        li =[0]*(mx +1)
        n = len(changed)
        if n % 2:
            return []
        for x in changed:
            li[x] +=1
        ans =[]
        if li[0]% 2 ==0:
            ans += [0]*(li[0]//2)
        else:
            return []
        for i in range(mx,0,-1):
            if li[i]:
                if i % 2:
                    return []
                else:
                    m = i//2
                    if li[m]>= li[i]:
                        ans += [m] *li[i]
                        li[m] -= li[i]
                    else:
                        return []
        return ans

Explain

此题解采用了计数排序的思路来解决问题。首先通过最大值创建一个足够大的数组 `li` 用于统计 `changed` 中每个元素的出现次数。首先，如果 `changed` 的长度不是偶数，则直接返回空数组，因为双倍数组的长度必须是偶数。接下来，特别处理 0 的情况，因为 0 的双倍还是 0，需要确保 0 的数量是偶数。然后从最大值开始向下遍历，对于每个 `i`，判断其一半 `i/2` 是否存在于 `li` 中，且数量是否足够。如果足够则将 `i/2` 加入结果数组 `ans` 中相应的次数，并减少 `li[i/2]` 的计数。如果在任何点出现不匹配，则返回空数组。这种方式有效地利用了计数数组来避免排序，从而提高效率。

时间复杂度: O(n + mx)

空间复杂度: O(mx)

class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        mx = max(changed)  # 找到 changed 中的最大值
        li = [0] * (mx + 1)  # 创建计数数组
        n = len(changed)
        if n % 2:  # 如果 changed 的长度不是偶数，直接返回空数组
            return []
        for x in changed:
            li[x] += 1  # 填充计数数组
        ans = []
        if li[0] % 2 == 0:  # 处理 0 的特殊情况
            ans += [0] * (li[0] // 2)
        else:
            return []
        for i in range(mx, 0, -1):  # 从最大值遍历到 1
            if li[i]:  # 如果当前值有计数
                if i % 2:  # 如果是奇数，不存在有效的原数组
                    return []
                else:
                    m = i // 2  # 找到当前值的一半
                    if li[m] >= li[i]:  # 如果一半的值的计数足够
                        ans += [m] * li[i]  # 加入到结果数组
                        li[m] -= li[i]  # 减少计数
                    else:
                        return []
        return ans

Explore

因为题目的目标是从一个包含双倍数的数组中还原出原数组。原数组中的每个元素都必须在双倍数组中以其原始数值和两倍数值的形式出现。对于0来说，其双倍也是0，因此在双倍数组中，0的数量必须是偶数，这样才能确保每个0都可以与另一个0配对，形成原始数组中的一个0。如果0的数量是奇数，则无法完全配对，意味着无法还原成有效的原数组。

如果输入数组changed的长度不是偶数，那么不能完全由原数组和其对应的双倍数组组成，因为原数组中每个元素和其对应的双倍数都应该出现两次。一个奇数长度的数组无法被完全分成这样的成对形式，因此无法从中完整地还原出原数组。这是基于题目要求，每个原始元素及其双倍必须出现，从而保证数组长度必须是偶数。

从最大值mx开始向下遍历直至0的原因是这样可以直接判断较大数的双倍关系是否成立，并且减少错误匹配的可能性。如果从0开始向上遍历，可能会先处理较小的数，而这些小数可能是较大数的一半，这样在遇到较大数时，它们的计数可能已经被错误地减少，从而导致错误的匹配。从大到小遍历可以保证当处理一个数时，所有可能的双倍数都已经被先前处理过，从而保持正确的计数和匹配。

在处理非零元素时，如果当前元素i是奇数，则返回空数组的逻辑是基于无法找到一个有效的原始数组元素m使得m的双倍等于i。题目要求能够从changed数组中找出原数组，使得每个元素的双倍也在changed数组中。对于奇数i，无法通过将任何整数m乘以2得到奇数（因为整数乘以2总是偶数），因此如果changed数组中包含奇数，则说明无法将该数组还原为每个元素及其双倍的形式，即无法找到一个合理的原数组。