力扣215.数组中第K大元素（堆排序、快排序）[javaScript]_力扣第k大元素

力扣215.数组中第K大元素（堆排序、快排序）[javaScript]

给定整数数组 nums 和整数 k，请返回数组中第k个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例1：

输入：[3,2,1,5,6,4] ,k=2

输出：5

示例2：

输入：[3,2,3,1,2,4,5,5,6],k=4

输出：4

首先这题需要第k大的元素，即将数组排序后，index+1下标的元素则是，第index+1大的元素。

需要时间复杂度为O(n)的算法。如果用常规的内置函数的排序很难达到这样的时间复杂度，所以我们考虑到使用堆排序和快排序这两种方法。其中堆排序在很多大厂的机试上需要会的。推荐优先理解堆排序。

---

堆排序

• 第 n 个元素的 左子节点 为 2*n+1

• 第 n 个元素的 右子节点 为 2*n+2

• 第 n 个元素的 父节点 为 (n-1)/2

• 最后一个非叶子节点为 Math.floor(arr.length/2)-1

  堆是具有以下性质的完全二叉树：

大顶堆：每个节点的值都 大于或等于 其左右孩子节点的值

注：没有要求左右值的大小关系

小顶堆：每个节点的值都 小于或等于 其左右孩子节点的值

上图中绿色框框就是构建一个大顶堆，将树里面最大一个数字提到树的最顶部。然后将顶部的数字放在树的最末尾并在后续的排除它，这样最后就得到一个升序的数组。

var findKthLargest = function(nums, k) {
    let heapSize = nums.length
    // 自下而上构建一颗大顶堆
    const buildMaxHeap = (nums, heapSize) => {
        for(let i= Math.floor(heapSize/2)-1;i>=0;i--) {
            maxHeapify(nums,i,heapSize)
        }
    }
    const swap = (a, i, j) => {
        let temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    // 从左向右，自上而下的调整节点
    const maxHeapify = (nums,i,heapSize) => {
        let l = i*2+1
        let r = i*2+2
        let largest = i
        if(l < heapSize && nums[l] > nums[largest]){
            largest = l
        }
        if(r<heapSize && nums[r] > nums[largest]) {
            largest = r 
        }
        if (largest !== i) {
            swap(nums, i, largest)
            maxHeapify(nums,largest, heapSize)
        }
    }
    buildMaxHeap(nums,heapSize)
    for(let i = nums.length-1;i>= nums.length-k+1;i--) {
        swap(nums, 0, i)
        --heapSize
        maxHeapify(nums, 0, heapSize)
    }
    return nums[0]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

总结思路

• 将无序序列构建成一个堆，根据升序降序需求选择大顶堆
• 将堆顶元素与末尾元素交换，将最大元素「沉」到数组末端
• 重新调整结构，使其满足堆定义，然后继续交换堆顶与当前末尾元素，反复执行调整、交换步骤，直到整个序列有序。

步骤

这里想说的几点注意事项（代码实现的关键思路）：

• 第一步构建初始堆：是自底向上构建，从最后一个非叶子节点开始。

• 第二步就是下沉操作让尾部元素与堆顶元素交换，最大值被放在数组末尾，并且缩小数组的length，不参与后面大顶堆的调整

• 第三步就是调整：是从上到下，从左到右,因为堆顶元素下沉到末尾了，要重新调整这颗大顶堆

---

快排序

快速排序的原理参考原文

• 在数组中选择一个元素，这个元素被称为基准（Pivot）。通常把数组中的第一个或最后一个元素作为基准。

• 然后，重新排列数组的元素，以使基准左侧的有元素都小于基准，而右侧的所有元素都大于基准。这一步称为分区。如果一个元素等于基准，那么在哪一侧都无关紧要。

• 针对基准的左侧和右侧分别重复这一过程，直到对数组完成排序。

如下图所示：

• 图中绿框框表示数组。黄色虚线背景表示随机选中的基数

在数组中随机选一位数字，进行大小比较，左右分区，分区之后产生的新数组，继续随机选择一个新数组，这样递归下去依次比较，最后得到每个数组都是一个数字。

const solveNbig = (arr, k) => {
    // 分区的代码
    function partition(arr, start, end) {
        // 以最后一个元素为基准或者随机选择一个
        const pivotValue = arr[end];
        let pivotIndex = start;
        for (let i = start; i < end; i++) {
          // 只有小于时候需要交换，其他时候就不需要交换
            if (arr[i] < pivotValue) {
                // 交换元素
                [arr[i], arr[pivotIndex]] = [arr[pivotIndex], arr[i]];
                // 移动到下一个元素
                pivotIndex++;
            }
        }
        // 把基准值放在中间
        [arr[pivotIndex], arr[end]] = [arr[end], arr[pivotIndex]]
        return pivotIndex;
    };
     /* 
        代码以最后一个元素为基准，用变量 pivotIndex 来跟踪“中间”位置，
        这个位置左侧的所有元素都比 pivotValue 小，而右侧的元素都比 pivotValue 大。
        最后一步把基准（最后一个元素）与 pivotIndex 交换。
    */
    // 递归代码
    function quickSort(arr, start, end) {
        // 终止条件
        if (start >= end) {
            return;
        }
        // 返回 pivotIndex
        let index = partition(arr, start, end);
        // 将相同的逻辑递归地用于左右子数组
        quickSort(arr, start, index - 1);
        quickSort(arr, index + 1, end);
    }
    quickSort(arr,0,arr.length-1);
    return arr[k-1];
}

let arr = [3, 2, 3, 1, 2, 4, 5, 5, 6];
let k = 4;
let res = solveNbig(arr, k);
console.log('res::
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/代码探险家/article/detail/735804