2007. Find Original Array From Doubled Array

An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.

array

class Solution {
public:
    vector<int> findOriginalArray(vector<int>& changed) {
        int maxE = *max_element(changed.begin(), changed.end()), cnt = changed.size();
        if(maxE & 1 or cnt & 1) return {};
        vector<int> arr(maxE + 1, 0);
        for(auto& c : changed) arr[c]++;
        changed.clear();
        if(arr[0]) {
            if(arr[0] & 1) return {};
            fill_n(back_inserter(changed), arr[0] >> 1, 0);
        }

        for(int i = 1; i <= maxE>>1; ++i) {
            if((arr[i * 2] -= arr[i]) < 0) return {};
            fill_n(back_inserter(changed), arr[i], i);
        }
        if(changed.size() != cnt / 2) return {};
        return changed;
    }
};

queue

class Solution {
public:
    vector<int> findOriginalArray(vector<int>& changed) {
        priority_queue<int, vector<int>, greater<int>> q(changed.begin(), changed.end());
        queue<int> doubleQ;
        changed.clear();
        while(!q.empty()) {
            while(!doubleQ.empty() and !q.empty() and doubleQ.front() == q.top()) {
                doubleQ.pop();
                q.pop();
            }
            if((!q.empty() and !doubleQ.empty() and doubleQ.front() < q.top()) or q.size() < doubleQ.size()) return {};
            if(!q.empty()) {
                changed.push_back(q.top());
                doubleQ.push(q.top() * 2);
                q.pop();
            }
        }
        if(!doubleQ.empty()) return {};
        return changed;
    }
};

map

class Solution {
public:
    vector<int> findOriginalArray(vector<int>& changed) {
        map<int, int> m;
        for(auto& c : changed) m[c]++;
        changed.clear();
        if(m.count(0)) {
            if(m[0] & 1) return {};
            fill_n(back_inserter(changed), m[0] >> 1, 0);
            m.erase(0);
        }
        for(auto& e : m) {
            if(m[e.first * 2] < e.second) return {};
            if(!(m[e.first * 2] -= e.second)) m.erase(e.first * 2);
            fill_n(back_inserter(changed), e.second, e.first);
        }
        return changed;
    }
};