題目

https://leetcode.com/problems/kth-largest-element-in-an-array/

---

題解

本題需要建立大頂堆。關(guān)于堆的數(shù)據(jù)結(jié)構(gòu)，需要知道：

堆

什么是堆？

堆 是一棵 完全二叉樹：即使它不是滿二叉樹，也是正在從左往右變滿的過程中。

1）堆結(jié)構(gòu)就是用數(shù)組實現(xiàn)的完全二叉樹結(jié)構(gòu)

2）完全二叉樹中，如果每棵子樹的 最大值都在頂部，是 大根堆

3）完全二叉樹中，如果每棵子樹的 最小值都在頂部，是 小根堆

4）堆結(jié)構(gòu)的 heapInsert 與 heapify 操作

5）堆結(jié)構(gòu)的增大和減少

6）優(yōu)先級隊列結(jié)構(gòu)，就是堆結(jié)構(gòu)

7）特點：由 N 個數(shù) 組成的堆，高度是 log(n)

如何用數(shù)組存放堆？

如果從 0 位置開始：

i 層，則

• 左孩子：2 * i + 1
• 右孩子：2 * i + 2
• 父節(jié)點：(i - 1) / 2

如果從 1 位置開始：

正是由于可以使用 位運算 來代替 算數(shù)運算，效率更高，所以有時候讓下標(biāo)從 1 開始。

• 左孩子：2 * i （i << 1）
• 右孩子：2 * i + 1 （i << 1 | 1）
• 父節(jié)點：i / 2 （i >> 1）

如何將數(shù)組轉(zhuǎn)化成大根堆？—— heapInsert 操作

每在 i 位置加入一個新的節(jié)點，都與它的 (i - 1) / 2 位置的父節(jié)點比較，如果比父節(jié)點大，則交換（并while比較父節(jié)點與父父節(jié)點）

private void heapInsert(int[] arr, int index) {while (arr[index] > arr[(index - 1) / 2]) {swap(arr, index, (index - 1) / 2);index = (index - 1) / 2;} } private void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp; }

如何返回并刪除大根堆的最大值，剩余數(shù)字依然保持大根堆？—— heapify 操作

將頂部元素取出

將大根堆的最后位置上的元素覆蓋到頂部

while 循環(huán)

如果左右孩子中較大的數(shù)比當(dāng)前節(jié)點更大，則交換當(dāng)前節(jié)點和較大的孩子節(jié)點

如果左孩子下標(biāo)越界，或左右孩子都不比當(dāng)前節(jié)點大，就停止

// 返回最大值，并在大根堆中把最大值刪掉，剩下的數(shù)依然保持大根堆形態(tài) public int pop() {int ans = heap[0];swap(heap, 0, --heapSize);heapify(heap, 0, heapSize);return ans; } // 從index位置開始，不斷的下沉，直到我的孩子都不再比我大，或者我已經(jīng)沒孩子了，就停止 private void heapify(int[] arr, int index, int heapSize) {int left = index * 2 + 1;while (left < heapSize) {// largest存儲左右孩子 較大者 的下標(biāo)int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;// largest存儲兩個孩子與父節(jié)點 較大者 的下標(biāo)largest = arr[largest] > arr[index] ? largest : index;if (largest == index) { // 不需要交換的情況break;}swap(arr, largest, index);index = largest;left = index * 2 + 1;} }

堆排序

先讓整個數(shù)組都變成大根堆結(jié)構(gòu)，建立堆的過程:

從上到下的方法，時間復(fù)雜度為O(N*logN)

從下到上的方法，時間復(fù)雜度為O(N)

把堆的最大值和堆末尾的值交換，然后減少堆的大小之后，再去調(diào)整堆，一直周而復(fù)始，時間復(fù)雜度為O(N*logN)

堆的大小減小成0之后，排序完成！

public static void heapSort(int[] arr) {if (arr == null || arr.length < 2) {return;}// 方法1：對數(shù)組進行堆排序 O(N*logN)for (int i = 0; i < arr.length; i++) { // O(N)heapInsert(arr, i); // O(logN)}// 方法2：僅將數(shù)組轉(zhuǎn)化成大頂堆 O(n) for (int i = arr.length - 1; i >= 0; i--) {heapify(arr, i, arr.length);} }

---

本題代碼

class Solution {int[] nums;int heapSize;public int findKthLargest(int[] nums, int k) {this.nums = nums;this.heapSize = nums.length;// 先讓整個數(shù)組變成大根堆結(jié)構(gòu)// 方法1：從上至下 對數(shù)組進行堆排序 O(N*logN) // for (int i = 0; i < nums.length; i++) // O(N) // heapInsert(nums, i); // O(logN)// 方法2：從下至上 僅將數(shù)組轉(zhuǎn)化成大頂堆 O(N)for (int i = nums.length - 1; i >= 0; i--)heapify(nums, i, nums.length);int result = -1;for (int i = 0; i < k; i++)result = pop();return result;}public int pop() {int max = nums[0];swap(nums, 0, --heapSize);heapify(nums, 0, heapSize);return max;}// 方法1 從上至下調(diào)整堆：每在i位置加入一個新的節(jié)點，都與它的(i-1)/2位置的父節(jié)點比較，如果比父節(jié)點大，則交換（并while比較父節(jié)點與父父節(jié)點）private void heapInsert(int[] arr, int index) {while (arr[index] > arr[(index - 1) / 2]) {swap(arr, index, (index - 1) / 2);index = (index - 1) / 2;}}// 方法2 從下至上調(diào)整堆：從index位置開始，不斷的下沉，直到我的孩子都不再比我大，或者我已經(jīng)沒孩子了，就停止public void heapify(int[] arr, int i, int heapSize) {int left = i * 2 + 1;while (left < heapSize) {int largest = left + 1 < heapSize && nums[left + 1] > nums[left] ? left + 1 : left; // 左右孩子較大者的下標(biāo)largest = nums[largest] > nums[i] ? largest : i; // 兩個孩子與父節(jié)點較大者的下標(biāo)if (largest == i) break; // 不需要交換的情況swap(arr, largest, i);i = largest; // 更新i使其下沉left = 2 * i + 1;}}private void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;} }

總結(jié)

以上是生活随笔為你收集整理的leetcode 215. Kth Largest Element in an Array | 215. 数组中的第K个最大元素（Java）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。