LeetCode:703. 数据流中的第 K 大元素
目录
题目描述:
分析:
解题代码:
小顶堆代码:
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();
}