题目描述
题目链接
一个整数数组original
可以转变成一个双倍数组changed
,转变方式为将original
中每个元素值乘以2加入数组中,然后将所有元素随机打乱。
给你一个数组changed
,如果change
是双倍数组,那么请你返回original
数组,否则请返回空数组。original
的元素可以以任意顺序返回。
题目分析
这题难点在于随机打乱,并且我们要根据一个元素去找另一个元素(二倍值)。我们可以对整个changed
进行排序,这样第一个元素肯定就不是二倍值,我们想判断它的二倍值是否存在,最简单粗暴的方法就是往后遍历,但是这样做效率肯定就很低,那么我们能想到一个查询为O(1)的方法——把他们用map保存起来,其中key是该元素值,value是这个元素出现的次数。
为什么要统计出现次数?我们判断某一个元素changed[i]
的二倍值是否存在,即其二倍值出现的次数map[2*changed[i]]
是否不为0。若存在,则将该元素放入original
中,并且将它的二倍值减1,因为我们不希望往后遍历的时候再去碰到这个二倍值,同时,因为这个元素已经被我们放进original
了,该元素出现的次数也要减1。
cpp代码
于是我们可以写出下面的代码:
class Solution {
public:vector<int> findOriginalArray(vector<int>& changed) {// 如果changed的元素个数不是2的倍数,则一定不是双倍数组if(!changed.size() % 2) return {};sort(changed.begin(), changed.end()); // 首先将changed排序unordered_map<int, int> map; // 利用map来记录每一个元素出现的次数for(int i : changed) {map[i]++; // 元素作为key,出现次数为value}vector<int> original;for(int j : changed) {if(map[j] != 0) {if((j && map[j * 2] != 0) || (!j && map[j] > 1)) { // 如果2*j在map中出现过,则说明有配对map[j * 2]--;original.push_back(j);map[j]--; //j出现次数也要-1,因为我们拿出了一个放进了original}else return{};}else continue;}return original;}
};
需要注意的是,我对元素值为0
的进行了单独的判断,也就是if
语句中的:j && map[j] > 1
。因为0的二倍值就是它自己,所以他的二倍值出现次数和本身出现次数都存放在map的key
为0
的value
中。