目录
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];}}
}
