2 ms·
Suppose I have a million clowns. Even if I want the funniest six in funniest order the optimal way to do that is to ask first to partition just the six funniest
by tialaramex 4y ago
Suppose I have a million clowns. Even if I want the funniest six in funniest order the optimal way to do that is to ask first to partition just the six funniest, and then sort those six finally. Sorting the other 999_994 clowns is pointless for this task, and will waste the vast majority of our run time.
- zabzonk 4y agoso, as i said, possibly write a specialised container to do that. but you are still going to need to read the million clowns, so maybe (i haven't investigated this) the best approach is to read the clowns, which you have to do anyway, and then see if they can be inserted into an array of the currently highest funniest (though i would never see clowns as being funny). i don't remember saying anything about sorting to solve this specific problem, only in the general case - perhaps i did not make this clear.