Top k

Given a list of n numbers, get the top k ones in O(n) time.

This problem is too easy to solve in O(n log n) time

def top_k_n_log_n(l, k):
    sl = sorted(l)
    return sl[-k:]

but o(n log n) solutions can be presented for partial credit. 😛

Advertisements

3 thoughts on “Top k

  1. Miles says:
    int* topk(int* begin, int* end, int k)
    {
    	std::nth_element(begin, end-k, end);
    	return end-k;
    }
    

    For example?

    Edited to format the code in a nicer way.

  2. […] [Answer to the problem in Top k.] […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s