返回数组中第k大的元素 def findk(x, k):

这里给出一种快速选择算法（Quickselect）的实现，可以在平均时间复杂度 O(n) 的情况下找到数组中第 k 大的元素：

import random

def findk(x, k):
    if k < 1 or k > len(x):
        return None
    
    pivot = random.choice(x)
    lows = [i for i in x if i < pivot]
    highs = [i for i in x if i > pivot]
    pivots = [i for i in x if i == pivot]
    
    if k <= len(highs):
        return findk(highs, k)
    elif k > len(highs) + len(pivots):
        return findk(lows, k - len(highs) - len(pivots))
    else:
        return pivots[0]

函数的实现思路是，首先随机选择一个元素作为枢轴（pivot），然后将数组划分为三部分：

- 小于枢轴的元素组成的子数组 lows
- 等于枢轴的元素组成的子数组 pivots
- 大于枢轴的元素组成的子数组 highs

如果 k 恰好等于 highs 的长度，那么枢轴就是第 k 大的元素；如果 k 小于 highs 的长度，那么第 k 大的元素就在 highs 中；否则，第 k 大的元素就在 lows 中，并且需要更新 k 的值为 k - len(highs) - len(pivots)。这样，就可以递归地在 lows 或 highs 中继续查找第 k 大的元素，直到找到为止。

需要注意的是，这种实现方式是基于随机化的，因此在最坏情况下的时间复杂度是 O(n^2)，但是这种情况非常罕见。在实际应用中，快速选择算法的表现通常都非常好。