打乱后的原数组与两倍数组：支持负数和零的恢复

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• changed为整数多重集，要求存在original使changed等于original与逐项2x的拼接再打乱。
• 无法恢复返回None，合法空数组返回[]；不要求恢复原始顺序。

解题路线

1. 非零x的两倍绝对值严格更大。按绝对值从小到大处理，当前未消费x不能是更小未处理数的两倍，因此必须作为原值，并消费2x。
2. 负数普通数值升序不满足该拓扑顺序，例如−4会先于−2，错误地要求−8。按abs排序同时处理正负。
3. 零的两倍仍是零，必须偶数次并成对消耗。不是从0计数中减两次当前c，否则会出现自更新错误。

手动走一遍

changed=[−4,−2,0,0,2,4]，恢复[0,−2,2]（顺序可不同）。[1,2,2,4]恢复[1,2]；[0,0,0,2]因零次数奇数不可行。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from collections import Counter


def restore(changed):
    if len(changed) % 2:
        return None
    counts, answer = Counter(changed), []
    for x in sorted(counts, key=abs):
        c = counts[x]
        if not c:
            continue
        if x == 0:
            if c % 2:
                return None
            answer.extend([0] * (c // 2))
            counts[0] = 0
        else:
            if counts[2 * x] < c:
                return None
            answer.extend([x] * c)
            counts[2 * x] -= c
            counts[x] = 0
    return answer

复杂度

O(dlogd+n)时间、O(d+n)空间含计数与返回，d为不同值数。按所有元素排序会是O(nlogn)，示例只排序计数键。

易错点与追问

容易失分的边界

• 不要要求所有数非负后才证明算法，却在接口接受负数。
• changed长度偶数是必要条件，远非充分条件。

继续深挖

• 如果倍数为−2，绝对值排序仍成立吗？
• 倍数为1、0或−1时为什么本配对证明失效，如何另分情况？