目录

题目描述:

分析:

解题代码:

小顶堆代码:

main代码:

---

题目描述:

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

• KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
• int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

示例 1：

输入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]

输出：[null, 4, 5, 5, 8, 8]

解释：

KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // 返回 4
kthLargest.add(5); // 返回 5
kthLargest.add(10); // 返回 5
kthLargest.add(9); // 返回 8
kthLargest.add(4); // 返回 8

示例 2：

输入：
["KthLargest", "add", "add", "add", "add"]
[[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]

输出：[null, 7, 7, 7, 8]

解释：

KthLargest kthLargest = new KthLargest(4, [7, 7, 7, 7, 8, 3]);
kthLargest.add(2); // 返回 7
kthLargest.add(10); // 返回 7
kthLargest.add(9); // 返回 7
kthLargest.add(9); // 返回 8

分析:

这个类似于LeetCode中的215数组的第K大元素,

1.小顶堆中存放K个数据,使得第K大元素就是堆顶元素

2.        如果小顶堆中小于K个元素,直接offer加入

        如果小顶堆中的元素大于K个元素,判满并判断堆顶的元素是否大于数组中剩余的元素,如果大于,先删除堆顶,再加入

        如果数组为空,直接返回,在add函数直接添加     

        若小顶堆堆顶元素大于等于当前元素,则直接丢弃当前元素       

解题代码:

小顶堆代码:

package LeetCode703;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();}public boolean isFull(){return size==array.length;}//建堆  把数组调整为大顶堆的形式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代码:

   private MinHeap heap;public LeetCode703(int k, int[] nums){heap=new MinHeap(k);if(nums.length==0){//数组为空的话，直接返回return ;}for(int i=0;i<nums.length;i++){if(heap.isFull()&&nums[i]>heap.peek()){ //超过K的时候，替换掉堆顶元素heap.poll();}heap.offer(nums[i]);}
//        System.out.println(heap);}public int add(int val){if(!heap.isFull()){//不足K，直接加入heap.offer(val);}else{if(val>heap.peek()){heap.replace(val);}}
//        System.out.println(heap);return heap.peek();}