To find the 100th number in O(n) will do.
On 11月10日, 下午11时09分, [EMAIL PROTECTED]
[EMAIL PROTECTED] wrote:
I consider 3 ways:
n=1 million.
1. use a 100 heap (n*log(100)?)
2. use a 1 million heap.(time O(nlogn))
3. use quicksort, each time, discard the less part. ( O(logn)?)
but I can't
I think 1) is good choice. for 3) its not O(lgn) it would be O(n) if u force the pivot to be n-100.Selection algorithm also wud work here (O(n)).if u know the range of numbers, u can use a bitmap(courtesy : programming pearls). Though its O(n), if the range is small, u neednot examine the full
