规则：一个原始数组，其中的每个数都乘 2 ，并加入到数组中，打乱顺序。
给一个数组，判断这个数组是不是乘 2 的数组。
这个题唯一有点绕的情况是：...2,4,8...
这个时候，要判断 4 是 2 的二倍，还是 8 的原始数据？我们不能继续搜索 1 或者 16 ，因为这样循环搜索，一层套一层很麻烦。
继续思考，如果这个数组是个乘 2 数组，那么当前最大的数，一定是原始数据乘 2 来的（最小的数，一定是原始数据，要乘 2）。
接下来看数据规模，$1 <= changed.length <= 10^5, 0 <= changed[i] <= 10^5$，这个级别的数据规模，$\mathcal{O}(n)$ 以上的算法大概是行不通的，当然我没有试过。同时，因为数组长度较小，数据密集，可以使用数组作为哈希表，在 CLRS 中这种哈希表被称为 direct-address table。
将数组中的数据记录到哈希表中，从最大的数开始。如果是奇数，那么这一定不是乘 2 数组，返回空数组。否则除以 2 得到原始数据，将原始数据加入到结果中，同时哈希表中两个数的出现次数减 1 ，避免重复计算。如果某一个数在哈希表中的值小于 0 ，说明这个数的 2 倍的出现次数，多于这个数的出现次数，这显然不是一个乘 2 数组，返回空数组。
使用以上算法处理更大的半个数组，此时哈希表中所有数的出现次数都应该是0，如果有数据不是0，那么就不是一个乘 2 数组。
class Solution {
public:
vector<int> findOriginalArray(vector<int>& changed) {
const int n = changed.size();
if (n & 1) return {};
int nums[100001];
memset(nums, 0, sizeof nums);
int maxnumber = -1;
for (const int a : changed) {
maxnumber = max(maxnumber, a);
++nums[a];
}
int idx = 0, i = maxnumber, stop = n >> 1;
vector<int> res;
while (idx < stop) {
if (nums[i] < 0) return {};
if (nums[i] == 0) {
--i;
continue;
}
if (i & 1) return {};
const int ori = i >> 1;
res.emplace_back(ori);
--nums[ori];
--nums[i];
++idx;
}
for (int i = 0; i < maxnumber; ++i)
if (nums[i] != 0) return {};
return res;
}
};