Medium

题目描述

一个整数数组 original 被转换为双倍数组 changed，转换过程是将 original 中每个元素的值乘以 2 后添加到数组末尾，然后随机打乱结果数组。

给定一个数组 changed，如果它是一个双倍数组，请返回 original。如果 changed 不是双倍数组，则返回空数组。original 中的元素可以按任意顺序返回。

示例 1：

输入：changed = [1,3,4,2,6,8]
输出：[1,3,4]
解释：一个可能的原始数组是 [1,3,4]：
- 1 的两倍是 1 * 2 = 2
- 3 的两倍是 3 * 2 = 6  
- 4 的两倍是 4 * 2 = 8
其他可能的原始数组有 [4,3,1] 或 [3,1,4]

示例 2：

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

示例 3：

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

约束条件：

  • 1 <= changed.length <= 10^5
  • 0 <= changed[i] <= 10^5

解题思路

解题思路

这道题的关键在于理解双倍数组的性质：如果一个数组是由原始数组转换而来的双倍数组，那么数组长度必须是偶数，且每个原始元素 x 都对应一个双倍元素 2x。

核心思路

  1. 排序 + 贪心：将数组排序后，从最小元素开始处理。最小元素肯定不可能是其他元素的双倍，因此必须是原始数组中的元素。

  2. 哈希表计数：使用哈希表记录每个元素的出现次数，对于每个原始元素，检查其双倍是否存在且数量足够。

算法步骤

  1. 首先检查数组长度是否为偶数，奇数长度直接返回空数组
  2. 使用哈希表统计每个元素的频次
  3. 将所有不同的元素按升序排序
  4. 对每个元素 x：
    • 如果 x 的频次为 0，跳过（已被消耗）
    • 检查 2x 是否存在且频次足够
    • 将 x 加入结果，同时减少 x 和 2x 的频次
  5. 检查是否所有元素都被正确配对

特别注意：0 是特殊情况，因为 0 的双倍还是 0，所以 0 的个数必须是偶数。

代码实现

class Solution {
public:
    vector<int> findOriginalArray(vector<int>& changed) {
        int n = changed.size();
        if (n % 2 == 1) return {};
        
        unordered_map<int, int> count;
        for (int num : changed) {
            count[num]++;
        }
        
        vector<int> keys;
        for (auto& p : count) {
            keys.push_back(p.first);
        }
        sort(keys.begin(), keys.end());
        
        vector<int> result;
        for (int key : keys) {
            if (count[key] == 0) continue;
            
            int doubled = key * 2;
            if (count[doubled] < count[key]) return {};
            
            for (int i = 0; i < count[key]; i++) {
                result.push_back(key);
            }
            count[doubled] -= count[key];
            count[key] = 0;
        }
        
        return result;
    }
};

class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        n = len(changed)
        if n % 2 == 1:
            return []
        
        count = Counter(changed)
        result = []
        
        for key in sorted(count.keys()):
            if count[key] == 0:
                continue
                
            doubled = key * 2
            if count[doubled] < count[key]:
                return []
            
            result.extend([key] * count[key])
            count[doubled] -= count[key]
            count[key] = 0
        
        return result

public class Solution {
    public int[] FindOriginalArray(int[] changed) {
        int n = changed.Length;
        if (n % 2 == 1) return new int[0];
        
        var count = new Dictionary<int, int>();
        foreach (int num in changed) {
            count[num] = count.GetValueOrDefault(num, 0) + 1;
        }
        
        var keys = count.Keys.ToList();
        keys.Sort();
        
        var result = new List<int>();
        foreach (int key in keys) {
            if (count[key] == 0) continue;
            
            int doubled = key * 2;
            if (!count.ContainsKey(doubled) || count[doubled] < count[key]) {
                return new int[0];
            }
            
            for (int i = 0; i < count[key]; i++) {
                result.Add(key);
            }
            count[doubled] -= count[key];
            count[key] = 0;
        }
        
        return result.ToArray();
    }
}

var findOriginalArray = function(changed) {
    if (changed.length % 2 !== 0) return [];
    
    const count = new Map();
    for (const num of changed) {
        count.set(num, (count.get(num) || 0) + 1);
    }
    
    const result = [];
    const sorted = [...changed].sort((a, b) => a - b);
    
    for (const num of sorted) {
        if (count.get(num) > 0) {
            const doubled = num * 2;
            if (count.get(doubled) > 0) {
                result.push(num);
                count.set(num, count.get(num) - 1);
                count.set(doubled, count.get(doubled) - 1);
            } else {
                return [];
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n log n)主要消耗在排序操作
空间复杂度O(n)哈希表存储元素频次

相关题目