目錄
LeetCode-215題
LeetCode-215題
給定整數數組nums和整數k，返回數組中第k個最大元素
public class Solution {/*** 這里是基于小頂堆這種數據結構來實現的*/public int findKthLargest(int[] nums, int k) {// 實例化一個小頂堆MinHeap minHeap = new MinHeap(k);// 往小頂堆中添加k個元素for (int i = 0; i < k; i++) {minHeap.offer(nums[i]);}// 添加k個元素之后for (int i = k; i < nums.length; i++) {// 遇到不大于堆頂元素的直接跳過不管，繼續下一個if (nums[i] <= minHeap.peek()) {continue;}// 遇到大于堆頂元素的就將其把堆頂元素替換minHeap.replace(nums[i]);}// 此時堆頂元素就是第k個最大元素return minHeap.peek();}/*** 自定義一個小頂堆*/private static class MinHeap {private final int[] container;private int size;public MinHeap(int capacity) {container = new int[capacity];}/*** 添加元素*/public boolean offer(int num) {if (size == container.length)return false;// 執行上浮操作siftUp(num);return true;}/*** 上浮*/private void siftUp(int num) {int child = size++;// 通過子節點找父節點位置int parent = (child - 1) >> 1;// 只要滿足條件就一直找并比較while (child > 0 && container[parent] > num) {container[child] = container[parent];child = parent;parent = (child - 1) >> 1;}// 新添加的元素放到合適的位置container[child] = num;}/*** 替換頂部元素*/public void replace(int num) {container[0] = num;// 執行下潛操作siftDown(0);}/*** 下潛*/private void siftDown(int parent) {// 通過父節點位置找左子節點和右子節點的位置int left = (parent << 1) + 1;int right = left + 1;// 只要滿足有任一子節點的值小于父節點的值就交換順序int min = parent;if (left < size && container[left] < container[min]) {min = left;}if (right < size && container[right] < container[min]) {min = right;}if (min != parent) {swap(parent, min);siftDown(min);}}/*** 交換i位置和j位置上的值*/private void swap(int i, int j) {if (i == j)return;container[i] = container[i] ^ container[j];container[j] = container[i] ^ container[j];container[i] = container[i] ^ container[j];}/*** 查看堆頂元素*/public int peek() {return container[0];}}
}
