Posted on

Submission

```class Solution {
public:
vector<int> findOriginalArray(vector<int>& changed) {
if(changed.size() % 2 == 1) return {};
vector<int> rets;   // odds firstly
multiset<int> mset{changed.begin(), changed.end()};

while(!mset.empty()) {
int cur = *mset.begin();
mset.erase(mset.begin());

auto it = mset.lower_bound(2 * cur);
if(it == mset.end() || *it != 2 * cur) return {};
rets.push_back(cur);
mset.erase(it);
}

return rets;
}
};

// for odd numbers: it should find the even ones
// for even numbers: start from the smallest number, find the doubled number```

Submission II

```class Solution {
public:
vector<int> findOriginalArray(vector<int>& changed) {
if(changed.size() % 2 == 1) return {};
vector<int> rets;   // odds firstly
multiset<int> evens;

for(int x: changed) {
if(x % 2 == 0) evens.insert(x);
else rets.push_back(x);
}

int m = rets.size();
for(int i = 0; i < m; ++i) {
int cur = rets[i];

auto it = evens.lower_bound(2 * cur);
if(it == evens.end() || *it != 2 * cur) return {};
evens.erase(it);
}

while(!evens.empty()) {
int cur = *evens.begin();
evens.erase(evens.begin());

auto it = evens.lower_bound(2 * cur);
if(it == evens.end() || *it != 2 * cur) return {};
rets.push_back(cur);
evens.erase(it);
}

return rets;
}
};

// for odd numbers: it should find the even ones
// for even numbers: start from the smallest number, find the doubled number```