题解 | #寻找第K大#

# -*- coding:utf-8 -*-
import random

class Solution:
    def findKth(self, a, n, K):
        # write code here
        def qSort(a, l, r):
            if l >= r: return
            i, j = l, r
            p = random.randint(l, r)
            a[p], a[l] = a[l], a[p]
            while i < j:
                while i < j and a[j] > a[l] : j -= 1 # 先从右往左
                while i < j and a[i] <= a[l]: i += 1 # 再从左往右
                a[i], a[j] = a[j], a[i]
            a[l], a[i] = a[i], a[l]
            qSort(a, l, i-1)
            qSort(a, i+1, r)
        qSort(a, 0, n-1)
        return a[-K]