mplode
BAN USER
Comments (4)
Reputation 10
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
I can solve it in O(nlogn). Use a min-heap of size k. Scan through the array and add the first k elements to the heap (maintaining the min-heap property as you add them). Then, for each successive element, if it is larger than the min-heap element (root) swap it with the root and call heapify. Then after scanning the input, return the root. This has worst cast O(nlogn) if the array is sorted in reverse order initially.
- mplode March 02, 2011Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Though, now that I think about it this is no better than sorting it and choosing the max-k element :(
- mplode March 02, 2011