第K大的數(shù)字

public class KthLargestNumber {/*** 尋找第k大的元素* @param array 待調(diào)整的堆* @param k 第幾大*/public static int findKthLargestNumber(int[] array, int k) {//1.用前k個元素構(gòu)建最小堆buildHeap(array, k);//2.繼續(xù)遍歷數(shù)組，和堆頂比較for (int i = k; i < array.length; i++) {if (array[i] > array[0]) {array[0] = array[i];downAdjust(array, 0, k);}}//3.返回堆頂元素return array[0];}/*** 構(gòu)建堆* @param array 待調(diào)整的堆* @param length 堆的有效大小*/private static void buildHeap(int[] array, int length) {// 從最后一個非葉子結(jié)點開始，依次下沉調(diào)整for (int i = (length - 2) / 2; i >= 0; i--) {downAdjust(array, i, length);}}/*** 下沉調(diào)整* @param array 待調(diào)整的堆* @param index 要下沉的結(jié)點* @param length 堆的有效大小*/private static void downAdjust(int[] array, int index, int length) {// temp保存父結(jié)點值，用于最后的賦值int temp = array[index];int childIndex = (2 * index) + 1;while (childIndex < length) {// 如果有右孩子，且右孩子小于左孩子的值，則定位到右孩子if (((childIndex + 1) < length) &&(array[childIndex + 1] < array[childIndex])) {childIndex++;}// 如果父結(jié)點小于任何一個孩子的值，直接跳出if (temp <= array[childIndex]) {break;}//無需真正交換，單向賦值即可array[index] = array[childIndex];index = childIndex;childIndex = (2 * childIndex) + 1;}array[index] = temp;}public static void main(String[] args) {int[] array = new int[] { 7, 5, 15, 3, 17, 2, 20, 24, 1, 9, 12, 8 };System.out.println(findKthLargestNumber(array, 5));} }

總結(jié)

以上是生活随笔為你收集整理的《漫画算法2》源码整理-7 第K大的数字的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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