晋中网站建设公司,做安防在哪个网站做广告呢,做的物流网站,可以做外包的网站如果对于堆不是太认识#xff0c;请点击#xff1a;堆的初步认识-CSDN博客 解题思路#xff1a; /*** h3求数组中第 K 大的元素/h3* p* 解体思路* ol* 1.向小顶堆放入前k个元素* 2.剩余元素* 若 堆顶元素, 则略过* …如果对于堆不是太认识请点击堆的初步认识-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 大元素使用堆并不是最佳选择可以采用快速选择算法
