wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Find K Smallest Numbers in Unsoreted array?
        
(Message started by: sumtatt on Jan 13^th, 2012, 6:43am)

Title: Find K Smallest Numbers in Unsoreted array?
Post by sumtatt on Jan 13^th, 2012, 6:43am

How to find 'k' smallest integer in an unsorted array without sorting the array?

i.e.

in a[10] = (1,4,10,70,9,99,72,13,6,100);
for k=3 it should give the elements (1,4,6).

Title: Re: Find K Smallest Numbers in Unsoreted array?
Post by towr on Jan 13^th, 2012, 8:25am

Do partial sorting. Like quicksort, but you only keep the part you're interested in without sorting the rest.
So for example, you might first pivot around 10, you get
1,4,10,9,6 and 70,90,99,72,13,100
The part with the small elements has more than 3 elements, so you only need to examine that part further.

You can guarantee a linear runtime using 'median of medians' to choose the pivot.

Title: Re: Find K Smallest Numbers in Unsoreted array?
Post by birbal on Jan 14^th, 2012, 9:58am

find kth smallest number using selection algorithm
(http://en.wikipedia.org/wiki/Selection_algorithm)

Now pick all elements <= kth element.

Title: Re: Find K Smallest Numbers in Unsoreted array?
Post by ashmish2 on Jan 28^th, 2012, 11:11am

build min-heap and remove the smallest element
do it K times
0(k * log(n))

Title: Re: Find K Smallest Numbers in Unsoreted array?
Post by towr on Jan 28^th, 2012, 11:50am

You should include building the min-heap, in which case it's O(max(k,n) log n).

Title: Re: Find K Smallest Numbers in Unsoreted array?
Post by ashmish2 on Jan 28^th, 2012, 12:14pm

I am assuming K <= n. hence O(K * log(n))

Title: Re: Find K Smallest Numbers in Unsoreted array?
Post by towr on Jan 28^th, 2012, 2:01pm

You're also assuming it doesn't cost you time to build the min-heap. But it does. So it's O(n log(n))

Title: Re: Find K Smallest Numbers in Unsoreted array?
Post by imithya on Apr 22^nd, 2012, 11:11am

Hi Towr,

In case you need to find the K elements which are smallest amongst the n provided, we should be bulidling a min-heap of size k. So the time complexity should be O(klgn).

Title: Re: Find K Smallest Numbers in Unsoreted array?
Post by towr on Apr 22^nd, 2012, 11:25am

I think you mean O(n log k); you need to handle all n elements one way or another.

Anyway, you can do it in linear time, plain O(n).

Title: Re: Find K Smallest Numbers in Unsoreted array?
Post by akasina9 on Nov 16^th, 2012, 12:28am

on 04/22/12 at 11:25:00, towr wrote:

Anyway, you can do it in linear time, plain O(n).

@towr: Can you please elaborate on the O(n) method.

Title: Re: Find K Smallest Numbers in Unsoreted array?
Post by towr on Nov 16^th, 2012, 5:32am

on 11/16/12 at 00:28:01, akasina9 wrote:

@towr: Can you please elaborate on the O(n) method.

See replies #1 and #2.