Again it’s been a while after previous post…

O(nlogn) – Sort
Sort the list, and retrieve the nth one.

O(n*k) – Partial Sort
There can be multiple ways to do partial sort, one of them being selective sort: loop the list – first cycle get the biggest one; second cycle get the second one etc. till the Kth cycle. On each cycle we can move the number to the front, so that l[0:K] is sorted after Kth cycle.

O(n*logk) – Binary Search
This can be a little bit tricky but the idea is like binary search – divide and conquer:

def findKth(l, left, right, k):
    pivot_pos = partition(l, left, right)
    la = pivot_pos - left + 1
    lb = right - pivot_pos
    if la > k:
        return findKth(l, left, pivot_pos, k)
    else:
        return findKth(l, pivot_pos + 1, right, k - la)

O(n*logk) – Use a data structure to track K numbers
The idea is: use a data structure to store first K numbers. Initially, put first K numbers in L to the data structure; then loop through the list: for each element, check if the min number of the data structure is less than it, if not then pass, else remove the min number in the datastructure, and put the number in. Apparently min heap is a valid data structure to do it. O(n*logk)

O(n) – bitvec
Again make use of bitvec if possible….