如果對于堆不是太認(rèn)識，請點(diǎn)擊：堆的初步認(rèn)識-CSDN博客

解題思路：

/*** <h3>求數(shù)組中第 K 大的元素</h3>* <p>* 解體思路* <ol>*     1.向小頂堆放入前k個元素*     2.剩余元素*         若 <= 堆頂元素, 則略過*         若 > 堆頂元素, 則替換堆頂元素*     3.這樣小頂堆始終保留的是到目前為止,前K大的元素*     4.循環(huán)結(jié)束, 堆頂元素即為第K大元素* </ol>*/

小頂堆（可刪去用不到代碼）

class MinHeap {int[] array;int size;public MinHeap(int capacity) {array = new int[capacity];}private void heapify() {for (int i = (size >> 1) - 1; i >= 0; i--) {down(i);}}public int poll() {swap(0, size - 1);size--;down(0);return array[size];}public int poll(int index) {swap(index, size - 1);size--;down(index);return array[size];}public int peek() {return array[0];}public boolean offer(int offered) {if (size == array.length) {return false;}up(offered);size++;return true;}public void replace(int replaced) {array[0] = replaced;down(0);}private void up(int offered) {int child = size;while (child > 0) {int parent = (child - 1) >> 1;if (offered < array[parent]) {array[child] = array[parent];} else {break;}child = parent;}array[child] = offered;}private void down(int parent) {int left = (parent << 1) + 1;int right = left + 1;int min = parent;if (left < size && array[left] < array[min]) {min = left;}if (right < size && array[right] < array[min]) {min = right;}if (min != parent) {swap(min, parent);down(min);}}// 交換兩個索引處的元素private void swap(int i, int j) {int t = array[i];array[i] = array[j];array[j] = t;}
}

題解

public int findKthLargest(int[] numbers, int k) {MinHeap heap = new MinHeap(k);for (int i = 0; i < k; i++) {heap.offer(numbers[i]);}for (int i = k; i < numbers.length; i++) {if(numbers[i] > heap.peek()){heap.replace(numbers[i]);}}return heap.peek();
}

注意哦：求數(shù)組中的第 K 大元素，使用堆并不是最佳選擇，可以采用快速選擇算法

?