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
