-- coding:utf-8 --

class Solution: def findKth(self, a, n, K): # write code here if not a or n<1 or K>n: return -1 start,end = 0,n-1 K = n - K while True: q = self.partition(a,start,end)

print(q)

        if q == K:
            return a[q]
        if q < K:
            start = q + 1
        else:
            end = q - 1
    return -1

def partition(self,a,start,end):
    if start==end:
        return start
    x = a[end]
    i = start - 1
    for j in range(start,end):
        if a[j] < x:
            i += 1
            a[i],a[j] = a[j],a[i]
    i += 1
    a[i],a[end] = a[end],a[i]
    return i