[面试手撕]查找第K大的元素：[数组][快排]

其实不一定需要排序，采用类似快排的想法，随机挑选划分成三堆：比P小的、P、大等于P的。
然后判断P在当前子序列中的位置距离，其右侧有几个比它大的:

1. k-1个比它大的，返回P即可；
2. 比k-1个少，在左侧序列中到k-1-offset个即可。offset是当前比P大的个数。
3. 比k-1个多，迭代右侧序列。

（详见代码，复杂度O(NlogN)）

def find_k(arr, k):
    def split(low, high, k=0):
        if low >= high:
            return arr[low]
        i, j, p = low, high, low
        while i < j:
            while i < j and arr[j] >= arr[p]:  # 找到右边第一个小的
                j -= 1
            while i < j and arr[i] <= arr[p]:  # 找到左边第一个大的
                i += 1
            arr[i], arr[j] = arr[j], arr[i]
        arr[p], arr[j] = arr[j], arr[p]  # 把哨兵和最后一个找到的j对换
        # split(low, i), split(i + 1, high)  # 加上这行就是快排
        offset = high-i  # 比 arr[i]大的有offset位
        if offset == k-1:  # 右边有k位则当前即为第k大的
            return arr[i]
        elif offset < k-1:
            return split(low, i-1, k-offset-1)
        else:
            return split(i+1, high, k)
    return split(0, len(arr) - 1, k)

print(find_k(eval(input()), 3))