[每日一水] 求数组中第k大的值

我又来氵了[捂脸笑哭]

对应力扣上应该是这个第 3 大的数字：
https://leetcode-cn.com/problems/third-maximum-number/

对应上了，但有没完全对应上，力扣那个更难一下，里边的数组有重复的：

输入：[2, 2, 3, 1]
输出：1
解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。

本篇博客仅仅适合，没有重复数据的题目hh

先上代码：

import numpy as np

# 给定数组长度
k = 50

# 生成给定数组
sort_array = np.arange(k)
np.random.shuffle(sort_array)

# 寻找第 k 大的元素(该元素应当小于给定数组长度)
kth = 40

if kth > k:
    raise NotImplementedError("")
    
def getKthEle(array, kth):
    
    # 最后一个元素出去(快速排序: 要么第一个元素, 要么随便挑一个元素, 或其他)
    current = array[-1]
    array = array[:-1]
    
    S_minus = []
    S_add   = []
    
    for ele in array:
        if ele < current:
            S_add.append(ele)
        if ele > current:
            S_minus.append(ele)
    
    if len(S_minus)+1 > kth:
        return getKthEle(np.array(S_minus), kth)
    if len(S_minus)+1 == kth:
        return current
    if len(S_minus)+1 < kth:
        return getKthEle(np.array(S_add), kth-len(S_minus)-1)


print(getKthEle(sort_array, 36))

其实就是个快速排序的想法，与前几天归并排序不同的是，归并排序是按照索引将数据分成两堆，而快速排序是按照某个数字的大小将数据分成两堆

对应到这道题就是，我要找某个数组中的第 k k k大的数字，现在随机挑一个数字 a a a (一般取第一个数字或者最后一个数字)，然后按照大小将分为两堆 S + S_{+} S+​和 S − S_{-} S−​，前者是比 a a a大的数字们，后者反之。

这时，我就知道了数字 a a a 的排名 r a n k a rank_{a} ranka​

若：
r a n k a = = k rank_{a} == k ranka​==k
那我可以直接将 a a a 返回

若：
r a n k a < k rank_{a} < k ranka​ 则递归调用，在 S − S_{-} S−​中寻找 第 ( k − r a n k a ) (k-rank_{a}) (k−ranka​)大的数

若：
r a n k a > k rank_{a}> k ranka​>k
则递归调用，在 S + S_{+} S+​中寻找 第 k k k大的数

相当于每次将数据"二分"(不是标准二分)，不断降低问题的 s i z e size size
要是 r a n k a rank_{a} ranka​ 每次都为 ∣ ∣ a r r a y ∣ ∣ || array || ∣∣array∣∣ (问题数组的长度)的一半就好了，即问题 s i z e size size 每次都变为原来的1/2
但是数字是随机选的，显然不一定能保证每次都是 1 / 2 1/2 1/2

但是他的时间复杂度是 O ( l o g n ) O(logn) O(logn)，证明过程我以后补上