LeetCode:215. 数组中的第K个最大元素

目录

题目描述:

分析:

解答代码:

小顶堆代码:

main:

---

题目描述:

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

分析:

//使用小顶堆
/*
1.向小顶堆放入k个元素
2.剩余元素:若小顶堆堆顶元素小于当前元素,则将堆顶元素替换为当前元素,然后从上向下调整堆若小顶堆堆顶元素大于等于当前元素,则直接丢弃当前元素
3.小顶堆存放k个元素,堆顶元素就是第k个最大的元素
* */

解答代码:

小顶堆代码:

package LeetCode;import java.util.Arrays;public class MinHeap {int [] array;int size;public MinHeap(int capacity){array=new int[capacity];}public MinHeap(int []array){this.array=array;size=array.length;heapify();}//建堆  把数组调整为大顶堆的形式private void heapify(){//找到最后一个非叶子节点  size/2-1 (size是从零开始计数)for(int i=size/2-1;i>=0;i--){down(i);}}//parent是下潜的元素,与两个子节点比较，如果比子节点大，则交换，然后继续下潜public void down(int parent) {int left=2*parent+1;int right=2*parent+2;int min=parent;if(left<size&&array[left]<array[min]){//left<size 是为了防止越界,在索引有意义的范围内进行比较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 temp=array[i];array[i]=array[j];array[j]=temp;}//获取堆顶元素public int peek(){if(size==0){return Integer.MIN_VALUE;}return array[0];}//删除堆顶元素/** 1.将堆顶元素与最后一个元素交换位置* 2.将最后一个元素删除* 3.然后从上向下调整堆* */public int poll(){if(size==0){return Integer.MIN_VALUE;}int result=array[0];swap(0,--size);down(0);array[size]=0;return result;}//删除指定元素public int poll(int index){int delete=array[index];swap(index,--size);down(index);array[size]=0;return delete;}//替换堆顶元素public void replace(int value){array[0]=value;down(0);}//堆的尾部添加元素public boolean offer(int value){if(size==array.length){return false;}up(value);size++;return true;}private void up(int value) {int child = size;while(child>0){int parent=(child-1)/2;if(array[parent]>value){array[child]=array[parent];child=parent;}else{break;}}array[child]=value;  //进入不了循环的在这进行插入}public String toString() {return Arrays.toString(array);}
}

main:

 public int findKthLargest(int[] nums, int k) {MinHeap heap=new MinHeap(k);for(int i=0;i<k;i++){heap.offer(nums[i]);}System.out.println(heap);for(int i=k;i<nums.length;i++){if(nums[i]>heap.peek()){heap.replace(nums[i]);}}return heap.peek();}