zdzapple
BAN USER
Comments (3)
Reputation 25
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
1
of 3 vote
good solution :)
we can do it in another way, it's more simple:
1. first sort the array by height from taller ones to shorter ones;
2. use the frontTaller as the index, insert it to the result list.
bool Compare(const Person& a, const Person& b)
{
if (a.height != b.height) return a.height > b.height;
return a.frontTaller < b.frontTaller;
}
list<Person> retrieveQueue(vector<Person>& v)
{
sort(v.begin(), v.end(), Compare());
list<Person> q;
for (int i = 0; i < v.size(); ++ i)
{
q.insert(q.begin() + v.frontTaller, q);
}
return q;
}
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
but the solution above is O(n^2).
- zdzapple February 20, 2014we can use BST to reduce to O(nlogn)