题解 | #寻找第K大#

注意，这里判断p==k不是p+1==k.

第K大 -> 第n-K+1小

如n=6，a = [1,2,3,4,5,6],第2大的数是5，第4小的数是4，第5小的数才对应5.
而partition返回的p -> 有0,...,p-1，一共p个数比nums[p]小，所以nums[p]是第p+1小的数，所以这里不用判断p+1==k，而是直接p==k.
在寻找最小的K个数中，则需要判断p+1==k，详见：https://blog.nowcoder.net/n/5d1b7a8073eb44eca5375560e48db77e

# -*- coding:utf-8 -*-

class Solution:
    def findKth(self, a, n, K):
        # write code here
        if K <=0 or K > n:
            return -2
        k = n-K
        def partition(nums, lo, hi):
            i,j = lo+1, hi
            p = lo
            while True:
                while i <= hi:
                    if nums[i] > nums[p]:
                        break
                    i += 1
                while j > lo:
                    if nums[j] < nums[p]:
                        break
                    j -= 1
                if i >= j:
                    break
                nums[i], nums[j] = nums[j], nums[i]
            nums[lo], nums[j] = nums[j], nums[lo]
            return j
        lo, hi = 0, n-1
        while(lo<=hi):
            p = partition(a, lo, hi)
#             print(lo, hi, p, k, a)
            if p == k:
                return a[p]
            elif p > k:
                hi = p-1
            elif p < k:
                lo = p+1
        return -1