-- coding:utf-8 --

class Solution: def findKth(self, a, n, K): # write code here

    # 快排
    def fast_order(arr, no_k):
        left, right= 0, len(arr)-1
        pivot = arr[0]
        if not arr:
            return arr
        while left < right:
            while left < right and arr[right] <= pivot:
                right -= 1
            arr[left] = arr[right]
            while left < right and arr[left] >= pivot:
                left += 1
            arr[right] = arr[left]
        arr[left] = pivot
        
        # 每一轮排序后，查找Kth的位置。 k-1 才是下标，用来和left下标比较。
        if left == no_k -1:
            return arr[left]
        elif left > no_k - 1:
            return fast_order(arr[:left], no_k)
            # 当 kth比left元素大时，需要重新定位kth在list切片里的位置。
        else:
            return fast_order(arr[left+1:], no_k-1-left)
        
    return fast_order(a, K)