堆--数组中第K大元素

如果对于堆不是太认识，请点击：堆的初步认识-CSDN博客

解题思路：

/*** <h3>求数组中第 K 大的元素</h3>* <p>* 解体思路* <ol>*     1.向小顶堆放入前k个元素*     2.剩余元素*         若 <= 堆顶元素, 则略过*         若 > 堆顶元素, 则替换堆顶元素*     3.这样小顶堆始终保留的是到目前为止,前K大的元素*     4.循环结束, 堆顶元素即为第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();
}

注意哦：求数组中的第 K 大元素，使用堆并不是最佳选择，可以采用快速选择算法