這是我參與8月更文挑戰的第8天,活動詳情檢視: 8月更文挑戰
題目描述

解題思路
本題如果直接再用API解題肯定是不行的,因為面試不可能考你API如何使用,前幾天寫過這個題目是通過快速排序寫的,這次我們采用堆排序,通過大頂堆的方式來求出第K個最大的元素,其實這類問題都屬于經典的TOP K問題,屬于面試的常考題。
1. 建構大頂堆
為什麼要建構大頂堆,是因為大頂堆的對頂元素是整個數組中最大的元素.我們正式利用這點來求解問題的。
- 建構大頂堆的第一步是從最後一個非葉子節點開始,一直周遊到根節點.
- 一個節點的左子節點是 2*n + 1.
- 一個節點的右子節點是 2*n + 2.
- 一個節點的父節點是(n-1) / 2 (向下取整)
- 一棵樹的最後一個非葉子節點是 Math.flool(nums.length/2)-1.
2. 将大頂堆下沉K-1次,得到的就是第K大的元素
假如,我們要求的是第一大的元素,K-1就是零,也就是說不需要進行下沉,此時的大頂堆的堆頂就是最大的元素。若K-1=2,隻需下沉兩次,堆頂就是我們的最大的元素。所謂的下沉就是将堆頂與末尾元素進行交換。然後将堆的長度減一之後繼續進行堆化。
解題代碼
// 通過大頂堆求解問題
var findKthLargest = function(nums, k) {
// 堆的大小
let heapSize = nums.length;
// 調用大頂堆函數
buildMaxHeap(nums,heapSize);
// 要想求第K大的元素,就需要将大頂堆下沉K-1次,每下沉一次進行一次重新的堆化;
for (let i = 0; i < k - 1; i++ ) {
swap(nums,0,nums.length - 1 - i);
// 将最後一個元素忽略,不參與堆化
nums
heapSize--;
// 從第0個元素開始繼續進行堆化
maxHeapify(nums,0,heapSize);
}
// 此時堆頂就是第K個最大元素
return nums[0]
// 建構大頂堆
function buildMaxHeap(nums,heapSize) {
for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
maxHeapify(nums,i,heapSize)
}
}
function maxHeapify(nums,i,heapSize) {
// 首先假定第i個是最大的
let max = i;
let leftChild = 2 * i + 1;
let rightChild = 2 * i + 2;
// 如果下标不越界(即子孩子存在),并且子節點小于第i個元素
if (leftChild < heapSize && nums[leftChild] > nums[max]) {
max = leftChild;
}
if (rightChild < heapSize && nums[rightChild] > nums[max]) {
max = rightChild;
}
// 判斷是否發生了交換
if (max !== i) {
swap(nums,i,max);
// 交換之後,從下面上來的元素的位置後面需要繼續進行堆化
maxHeapify(nums,max,heapSize);
}
}
function swap (nums,i,j) {
let temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
};
findKthLargest([8,5,0,3,7,1,2], 3)
複制代碼
題目反思
- 學會使用大頂堆的方式來求解TOP K問題。
- 本題的思路也是解決堆排序的核心思路。