力扣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
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);
}
}
}
好文推荐
您阅读本篇文章共花了：
发表评论