215. 数组中的第K个最大元素

一、topk问题

考察的核心是可以进行topk排序算法。即不一定要全部排序好再去拿，只针对部分元素进行排序，解决topk问题的排序算法有快速排序、堆排序。

二、代码实现

1、调库函数sort()

var findKthLargest = function(nums, k) {
    
    nums.sort((a,b) => b-a);
     return nums[k-1];

};

2、快速排序

a、思想

快排的思想，以及时间复杂读的分析

1、划分操作：选择一个基准（通常选择第一个或者是最后一个元素）。然后从右往左进行遍历，直到找到一个比基准小的元素，将它放到左边。从左往右遍历，直到找到一个比基准大的元素，将它放到右边。这样当控制左右遍历的指针相遇时，停止遍历。这个位置就是基准的最后位置。
2、递归操作：划分之后，基准左边是比它小的数字，基准右边是比它大的数字。所以分别在基准的左右两边进行划分操作。

var quicksort = function(nums,low,high){
    if(low < high){
        let index = partition(nums,low,high)
        // 以第一轮得出的index为基准划分出左半区和右半区 对数组的左半区进行递归 将其全部变为有序
        quicksort(nums,low,index-1);
        quicksort(nums,index+1,high);
        }
    return nums;
};

var partition = function(nums,low,high){
    // 选定第一个元素为基准值 把它拿出来 即为“挖坑”.low和high就是指向左右两边的指针
    // let pivot = nums[low];
    
    // 更好的基准选择,用random取low-high之间的随机整数
    let pivot_idx = Math.floor(Math.random()*(high-low+1))+low;
    
    // pivot放置到最左边,两个值是相互替换。
    nums[low], nums[pivot_idx] = nums[pivot_idx], nums[low] ;    
    let pivot = nums[low];
    
    // 开始遍历
    while(low < high){
        // 挖了坑就需要填坑~从high指针开始向左找
        while (low < high && nums[high] >= pivot) high--;
        // 一旦找到比坑对应值pivot小的 就扔到low那侧的坑里
        nums[low] = nums[high];

        while (low < high && nums[low] < pivot) low++;
        nums[high] = nums[low];
    }
    // 经过上面的不断迭代 low===high 此时这个位置即为基准位置
    nums[low] = pivot;
    // 分区成功！返回定海神针~（此时low=high哦~）
    return low;
};

b、本题的代码实现

直接利用快排划分之后的index,和k-1 进行比较。

1. 检查一下，index是不是为 len(nums) - k,如果是，就直接返回。 如果index比len(nums)
2. 如果index比len(nums) -k要小，说明我们要找的数在右半边，我们只对右半边进行快速排序，左半边就不管了。
3. 如果index比len(nums) - k要大，说明我们要找的数在左半边，我们只对左半边进行快速排序，忽略右半边。

var findKthLargest = function(nums, k) {
    const n = nums.length;
    const target_index = n-k;
    let left = 0,
        right = n-1;
    
    // 注意只有一个元素的用例
    while(left <= right){
        // 目的是反复的调整区间，得到目标中的index。所以是放在循环里面
        const index = partition(nums,left,right);
        
        // 将index和n-k相比
        if(index == target_index){
            return nums[target_index];
        }
        // n-k小了，就需要到左边去找
        else if(index > target_index){
           right = index-1;
        }
        else{
            left = index+1;
        }        
    }   

};

// 进行划分
var partition = function(nums,low,high){
    // 选定第一个元素为基准值 把它拿出来 即为“挖坑”.low和high就是指向左右两边的指针
    // let pivot = nums[low];
    
    // 更好的基准选择,用random取low-high之间的随机整数
    let pivot_idx = Math.floor(Math.random()*(high-low+1))+low;
    
    // pivot放置到最左边,两个值是相互替换。
    nums[low], nums[pivot_idx] = nums[pivot_idx], nums[low] ;    
    let pivot = nums[low];
    
    // 开始遍历
    while(low < high){
        // 挖了坑就需要填坑~从high指针开始向左找
        while (low < high && nums[high] >= pivot) high--;
        // 一旦找到比坑对应值pivot小的 就扔到low那侧的坑里
        nums[low] = nums[high];

        while (low < high && nums[low] < pivot) low++;
        nums[high] = nums[low];
    }
    // 经过上面的不断迭代 low===high 此时这个位置即为基准位置
    nums[low] = pivot;
    // 分区成功！返回定海神针~（此时low=high哦~）
    return low;
};

3、堆排序

a、思想

各种排序算法
堆排序解决topk问题

b、本题的代码实现

使用堆排序来解决这个问题——建立一个大顶堆，做k−1 次删除操作后,堆顶元素就是我们要找的答案（堆排序过程中，不全部下沉，下沉nums.length-k+1,然后堆顶可以拿到我们top k答案了）

class Solution:
    def findKthLargest(self, nums, k) -> int:
        n = len(nums)
        self.build_maxHeap(nums)
        # 用大顶堆的顶点元素nums[0] 和末尾元素nums[n-1-i] 进行交换，即依次删除最大的元素。
        # 删除k-1个元素，那么顶点就是最大的
        for i in range(k-1):
            nums[0], nums[n-1-i] = nums[n-1-i], nums[0]
            self.adjust_down(nums, 0, n-1-i-1)
        return nums[0]


    def build_maxHeap(self, nums):
        n = len(nums)
        # 从最后一个非叶子节点开始从下至上调整
        for root in range(n//2 -1, -1, -1):
            self.adjust_down(nums, root, n - 1)

    # hi是节点的最大序号下标，即len(nums) - 1 （n-1）
    # root是根节点，从最后一个非叶节点从下至上遍历
    def adjust_down(self, nums, root, hi) :
        if root > hi:
            return
        t = nums[root]
        # child是左子树
        child = 2 * root + 1
        while child <= hi:
            # 如果存在右子树，则左右子树的值进行比较，选择最大的
            if child + 1 <= hi and nums[child] < nums[child + 1]:
                child += 1
            # 根节点不是最大的，就把值以及序号进行交换
            if t >= nums[child]:
                break
            nums[root] = nums[child]
            root = child
            # 由于进行了交换，可能会导致下一层的节点相对大小的变化，所以还需要再次检查下一层的变化
            child = 2 * root + 1
        # 当child的序号越界，即节点没有左子树。那么根节点的值就是放在叶子节点。如果没有这一行，那么当没有左子树的时候，会出错。
        nums[root] = t