NC88 寻找第K大

描述 有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。

给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。 要求：时间复杂度 O(nlogn)，空间复杂度 O(1) 数据范围：0≤n≤1000， 1≤K≤n，数组中每个元素满足 0≤val≤10000000

思路：用堆，最大堆，我对于堆的知识已经完全完全忘记了，这次是在网上看了之后，再自己改进了一点点。最大堆就是根节点的值比子节点都大。如果下层节点能保证比子孙节点大，那么其父节点只需要比较自己的左右子节点就可以保证比子孙节点都大。所以在创建最大堆的时候，需要从叶子节点往上开始创建。 堆是数组，根据下标来找父节点和子节点。下标为0的节点为根节点，其子节点下标为1，2。1的子节点下标为3、4，2的子节点为5、6，3的子节点下标为7、8，4的子节点下标为9，10。由此找到规律下标为i的子节点下标为2i+1、2i+2，父节点为(i+1)/2-1。 我们没有办法确定倒数第二层（最后的非叶子节点层）的第一个元素，但是我们可以找到最后一个非叶子节点，因为我们知道最后一个节点的下标。所以我们从右往左遍历。

数组长度为n，最后一个节点的下标为n-1，最后一个非叶子节点的下标（即最后一个节点的父节点下标）为（n-1+1)/2-1=n/2-1。之后从右往左，从下往上创建，

每一个节点都只需要比较自身节点（根节点）和左右子节点的值，如果根节点就是最大值，则不需要交换值。如果左右子节点有更大的值，记录最大值的下标largest，根据下标将最大值和根节点进行交换。 for i in range(n // 2 - 1,-1,-1):self.createMaxStack(a,n,i) 这就创建了最大堆。第一次创建需要从最后一个非叶子节点遍历到a[0]。所以循环下标从n // 2 - 1到0，每次循环i要-1.

之后还需要进行排序，最大堆创建后，根节点的值最大，根节点为a[0]，我们将a[0]，和数组最后a[n-1-j] (j表示循环次数，第一个j为0，第二次a[0]是第二大的数，j为1，a[0]放a[n-2])的值进行交换，再将剩下的数组a[0]到a[n-2-j]（每次循环数组长度-1，数组长度为n-1-j）进行最大堆的创建。

因为之前已经创建好了最大堆，也就是大部分是有序的，只有根节点可能无序，所以再次创建的时候，只需要一层一层将根节点放到合适位置。根节点在0的位置，所以从0开始,a[0]和左右子节点比较，如果左节点最大，a[0]和左节点交换，再比较左节点和其子节点的值。如果根节点是最大值，就不用再往下了。循环次数最大为层数（即logn）。

因为需要找第K大的值，所以需要进行K次最大堆的创建，a[0]和最后一个值交换需要进行K-1次，最后一次不需要交换，a[0]就是我们需要的值。

特别注意，当K=n-1时，最后一次循环(j=K-2=n-3)后，交换a[0]和a[2]，不会再对a[0]和a[1]进行排序，因为createMaxStack 方法中的while循环条件不满足。所以需要对K=n-1的情况进行单独判断。仅判断a[0]和a[1]即可

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param a int整型一维数组 
# @param n int整型 
# @param K int整型 
# @return int整型
#
class Solution:
    @staticmethod
    def createMaxStack(a,l,i):
        while i < ((l - 1) // 2):
            largest = i
            if (a[i] < a[2*i+1]):
                largest = 2*i+1
            if (a[largest] < a[2*i+2]):
                largest = 2*i+2
            if largest != i:
                a[i],a[largest] = a[largest],a[i]
                i = largest
            else:
                break
    def findKth(self , a: List[int], n: int, K: int) -> int:
        # write code here
        for i in range(n // 2 - 1,-1,-1):
            self.createMaxStack(a, n, i)
        for j in range(K-1):
            a[0],a[n-1-j] = a[n-1-j],a[0]
            self.createMaxStack(a,n - 1 - j,0)
        if (K == n - 1) & (a[0] < a[1]):
            a[0],a[1] = a[1],a[0]
        return a[0]