Author |
Topic: Find K Smallest Numbers in Unsoreted array? (Read 9654 times) |
|
sumtatt
Newbie
Gender: 
Posts: 23
|
 |
Find K Smallest Numbers in Unsoreted array?
« on: Jan 13th, 2012, 6:43am » |
 Quote  Modify
|
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).
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Find K Smallest Numbers in Unsoreted array?
« Reply #1 on: Jan 13th, 2012, 8:25am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Find K Smallest Numbers in Unsoreted array?
« Reply #2 on: Jan 14th, 2012, 9:58am » |
Quote Modify
|
find kth smallest number using selection algorithm
(http://en.wikipedia.org/wiki/Selection_algorithm)
Now pick all elements <= kth element.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
ashmish2
Newbie
Posts: 12
|
|
Re: Find K Smallest Numbers in Unsoreted array?
« Reply #3 on: Jan 28th, 2012, 11:11am » |
Quote Modify
|
build min-heap and remove the smallest element
do it K times
0(k * log(n))
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Find K Smallest Numbers in Unsoreted array?
« Reply #4 on: Jan 28th, 2012, 11:50am » |
Quote Modify
|
You should include building the min-heap, in which case it's O(max(k,n) log n).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ashmish2
Newbie
Posts: 12
|
|
Re: Find K Smallest Numbers in Unsoreted array?
« Reply #5 on: Jan 28th, 2012, 12:14pm » |
Quote Modify
|
I am assuming K <= n. hence O(K * log(n))
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Find K Smallest Numbers in Unsoreted array?
« Reply #6 on: Jan 28th, 2012, 2:01pm » |
Quote Modify
|
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))
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
imithya
Newbie
Gender: 
Posts: 1
|
|
Re: Find K Smallest Numbers in Unsoreted array?
« Reply #7 on: Apr 22nd, 2012, 11:11am » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Find K Smallest Numbers in Unsoreted array?
« Reply #8 on: Apr 22nd, 2012, 11:25am » |
Quote Modify
|
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).
|
| « Last Edit: Apr 22nd, 2012, 11:26am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
akasina9
Newbie
x = 0x2B | ~ 0x2B. x is the question
Gender:
Posts: 9
|
|
Re: Find K Smallest Numbers in Unsoreted array?
« Reply #9 on: Nov 16th, 2012, 12:28am » |
Quote Modify
|
on Apr 22nd, 2012, 11:25am, towr wrote:| Anyway, you can do it in linear time, plain O(n). |
|
@towr: Can you please elaborate on the O(n) method.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Find K Smallest Numbers in Unsoreted array?
« Reply #10 on: Nov 16th, 2012, 5:32am » |
Quote Modify
|
on Nov 16th, 2012, 12:28am, akasina9 wrote:| @towr: Can you please elaborate on the O(n) method. |
|
See replies #1 and #2.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print