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

力扣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  nums[largest]){
            largest = l
        }
        if(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]
};

总结思路

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

步骤

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

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

• 第二步就是下沉操作让尾部元素与堆顶元素交换，最大值被放在数组末尾，并且缩小数组的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::👉', res); // res::👉 3

其中quickSort可以更换成循环实现递归quickSortIterative

快速排序的递归方法更加直观。但是用循环实现快速排序是一个相对常见的面试题。

与大多数的递归到循环的转换方案一样，最先想到的是用栈来模拟递归调用。这样做可以重用一些我们熟悉的递归逻辑，并在循环中使用。

我们需要一种跟踪剩下的未排序子数组的方法。一种方法是简单地把“成对”的元素保留在堆栈中，用来表示给定未排序子数组的 start 和 end。

JavaScript 没有显式的栈数据结构，但是数组支持 push() 和 pop() 函数。但是不支持 peek()函数，所以必须用 stack [stack.length-1] 手动检查栈顶。

// 循环实现递归
function quickSortIterative(arr1) {
    // 用push()和pop()函数创建一个将作为栈使用的数组
    stack = [];
    // 将整个初始数组做为“未排序的子数组”
    stack.push(0);
    stack.push(arr1.length - 1);
    // 没有显式的peek()函数
    // 只要存在未排序的子数组，就重复循环
    while (stack[stack.length - 1] >= 0) {
        // 提取顶部未排序的子数组
        end = stack.pop();
        start = stack.pop();
        pivotIndex = partition(arr1, start, end);
        // 如果基准的左侧有未排序的元素，
        // 则将该子数组添加到栈中，以便稍后对其进行排序
        if (pivotIndex - 1 > start) {
            stack.push(start);
            stack.push(pivotIndex - 1);
        }
        // 如果基准的右侧有未排序的元素，
        // 则将该子数组添加到栈中，以便稍后对其进行排序
        if (pivotIndex + 1 < end) {
            stack.push(pivotIndex + 1);
            stack.push(end);
        }
    }
}