【Leetcode】2007. 从双倍数组中还原原数组

题目描述

题目链接
一个整数数组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;
    }
};