By sonic0002
via pixelstech.net
Published: Jan 13 2013 / 10:14
This is an classical question, the general solution to this question is first using sorting algorithm to sort the array, then get the Kth number in the array, the complexity is O(nlogn), we can also use selective sort or head sort to, the complexity of selective sort is O(kn) and heap sort is O(nlogk). The better solution is to use quick sort to find the kth smallest number, the complexity is O(n), the worst case cost is O(n^2). But today we introduce one more solution which has the worst case cost O(n).
Add your comment
