https://leetcode.cn/problems/find-original-array-from-doubled-array/description/?envType=daily-question&envId=2024-04-11

队列

对数组进行排序后从小到大遍历数组，每个元素和队列头进行比较。如果队列为空或不是队列头的两倍，则将该元素入队；如果该元素是队列头的两倍，则队列头是原数组的一个元素；最后队列为空则表明该数组是双倍数组。

std::vector<int> findOriginalArray(std::vector<int>& changed) {
    if (changed.size() % 2 == 1)
        return {};

    std::queue<int> q;
    std::vector<int> res;
    std::sort(changed.begin(), changed.end());

    for (const auto& e : changed) {
        if (q.empty() || e != q.front() * 2) {
            q.push(e);
        } else {
            res.push_back(q.front());
            q.pop();
        }
    }

    return q.empty() ? res : std::vector<int>();
}

时间复杂度 $O(nlogn)$ ，空间复杂度 $O(n)$ ，其中 $n$ 为数组的长度。

数组

题目的范围是 $10^5$ ，可以开一个 count 数组来存所有数出现的次数，然后遍历 count 数组，如果一个数的频数大于零且其两倍数也存在，则该数为原数组中的一员；如果找不到它的两倍数，则该数组不是双倍数组。

std::vector<int> findOriginalArray2(std::vector<int>& changed) {
    if (changed.size() % 2 == 1)
        return {};

    const int MAX_NUM = 1e5 + 1;

    int count[MAX_NUM];
    memset(count, 0, sizeof(count));
    for (const auto &x : changed)
        ++count[x];

    if (count[0] & 1)
        return {};

    std::vector<int> res(count[0] >> 1, 0);
    for (int i = 1; i < MAX_NUM; ++i) {
        if (count[i] == 0)
            continue;

        if (count[i] < 0 || 2 * i >= MAX_NUM)
            return {};

        count[2 * i] -= count[i];
        while (count[i]--)
            res.push_back(i);
    }

    return res;
}

时间复杂度可以降到 $O(n)$ 。