使用堆排序來解決《亂序數(shù)組第k大的數(shù)字》
先放上代碼（雖然leetcode要求O(n)，但是堆排序是O(nlogn)）
`class Solution {
public int findKthLargest(int[] nums, int k) {
int heapSize = nums.length;
buildHeap(nums, heapSize);
for(int i = nums.length - 1; i >= nums.length - k + 1; i--) {
swap(nums, 0, i);
heapSize--;
buildHeap(nums, heapSize);
}
return nums[0];
}
public void buildHeap(int[] nums, int heapSize) {
for(int i = heapSize / 2 - 1; i >= 0; i--) {
maximum(nums, i, heapSize);
}
}
public void maximum(int[] nums, int root, int heapSize) {
int lChild = root * 2 + 1;
int rChild = root * 2 + 2;
int largest = root;
if (lChild < heapSize && nums[lChild] > nums[largest]) {
largest = lChild;
}
if (rChild < heapSize && nums[rChild] > nums[largest]) {
largest = rChild;
}
// 如果largest不再是入?yún)⒛莻€根節(jié)點，說明有子節(jié)點比它大，要換，換了之后繼續(xù)往下遞歸看還有沒有
if (largest != root) {
swap(nums, root, largest);
maximum(nums, root, largest);
}
}
public void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}`文章來源：http://www.zghlxwxcb.cn/news/detail-620915.html
比較有收獲的幾個點：文章來源地址http://www.zghlxwxcb.cn/news/detail-620915.html
- 堆里面兒子節(jié)點是父親節(jié)點n的n2+1和n2+2
- 刪除堆的堆頂是通過把堆頂元素和堆最后的元素交換，并且heapSize--來實現(xiàn)的
- 如果有兒子節(jié)點比父親節(jié)點大，那么需要交換父親節(jié)點和這個兒子節(jié)點，并且繼續(xù)將交換之后新的兒子節(jié)點作為新的根節(jié)點往下遞歸判斷
- 可以從heapSize/2這個節(jié)點開始判斷，并不斷--，最后得到的數(shù)組[0]就是正確的堆頂，進行進一步處理即可
到了這里，關于找出亂序數(shù)組第k大的數(shù)字（堆排序?qū)觯┑奈恼戮徒榻B完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
![【基礎算法】[PTA]-找出不是兩個數(shù)組共有的元素](https://imgs.yssmx.com/Uploads/2024/02/757956-1.gif)
