Loading... > https://leetcode.cn/problems/find-original-array-from-doubled-array/description/?envType=daily-question&envId=2024-04-11 ### 队列 对数组进行排序后从小到大遍历数组，每个元素和队列头进行比较。如果队列为空或不是队列头的两倍，则将该元素入队；如果该元素是队列头的两倍，则队列头是原数组的一个元素；最后队列为空则表明该数组是双倍数组。 ```c++ 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 数组，如果一个数的频数大于零且其两倍数也存在，则该数为原数组中的一员；如果找不到它的两倍数，则该数组不是双倍数组。 ```c++ 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)$ 。 最后修改：2024 年 05 月 06 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏