jh******@gmail.com said:
I have readed a book, there is a sentence like this:"Suppose you
have a group of n numbers and would like to determine the kth largest",
i want to know how to do it.i can't understand
I am a newcomer,and i have apologized for posting it on wrong place!
The comp.programming newsgroup would probably be a better match for your
question, but briefly, I suggest that your first attempt should work
something like this:
Set up an array of k numbers.
Populate the array with the first k numbers from your input.
Sort the array, with the lowest value being first in the array.
For each of the remaining (n - k) numbers, do this:
Compare the new number with the first element in the array.
If it is smaller or equal:
Discard it.
Otherwise:
Replace that element with the new number.
Taking care not to run off the end of the array...
While the new number is greater than the element to its right:
Swap the new number with the one to its right
At the end of this process, the kth largest number will be in position 0 of
the array.
Once you have a working solution, you will probably want to find ways to
improve its performance. But for now, the most important thing is to get
something that works. If you get stuck, let us know, and show us your best
attempt so far.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
