Kth maximum element in unsorted collection

Kode Log

Finding the Kth maximum element in an unsorted array doesn’t seem to be a big deal. Because, we know that finding the maximum and if we keep on eliminating the largest element from the array. And this we will take us to the Kth maximum element in an array. But this solution is of order O(n2). Can it be done in linear way?

Yes. Well, almost.

Have a look at the following method written in Java.

Generalizing into an algorithm

Calling FindKthMax(int[] input, int k)

1. Pick randomly a pivot a from input, lets call the selected pivot element – a.

2. Partition the n numbers into two sets:

* S – all the numbers smaller than a

* L – all the numbers larger than a

3. If |L| = k – 1 then a is the required K-median. Return a.

4. If |L| < k –…

View original post 96 more words

Advertisements
Standard

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