算法：优先队列-实战
实战的题目都是leetcode的题目。
目录
leetcode:703实时判断数据流中第K大的元素
方法一，直接快速排序
方法二、创建长度为K的数组，判断最小元素
第三种方法：运用小顶堆代替 长度为K的数组 ，判断最小元素
leetcode:239返回滑动窗口内的最大值
方法一、优先队列（大顶堆）
方法二、迭代前K个元素，找出最大值
leetcode:703实时判断数据流中第K大的元素
方法一，直接快速排序
解题思路
这个arr数组要是比较小，可以直接用快速排序，再输出第K大的值。时间复杂度O(N*K*logk)
class KthLargest {
private int[] nums; //保存数组
private int k; //最大值K
private int size; //当前下标
public KthLargest(int k, int[] nums) {
this.k = k;
this.nums = nums;
size = nums.length;
}
public int add(int val) {
nums = Arrays.copyOf(nums, size == 0 ? 1 : size + 1); //每次扩容一个数组位
nums[size] = val;
size++;
Arrays.sort(nums); //快速排序
if (k > nums.length) {
return 0;
}
return nums[nums.length - k];
}
}方法二、创建长度为K的数组，判断最小元素
解题思路
创建一个长度为k的数组，这个长度为K的数组，数组内容每次发生改变都快排一下，把最小值放在数组[0] 位上，每次传入的数字和数组[i++]比较一下，根据结果，决定是否存入和返回。存入则必须再次排序 ，保证数组最小值 等于 第K大的元素。
class KthLargest {
private int [] nums;
private int k ;
private int size;
public KthLargest(int k, int[] nums) {
this.k = k-1; //下标是从0开始的，个数是从1开始的
this.nums = new int[k];
for (int num:nums) {
add(num);
}
}
public int add(int val) {
if (size < k) { //判断数组K个位置是否存入元素
nums[size++] = val;
} else if (size == k) { //数组K个位置都存入元数，则快排一下 ，为了后面迭代方便
nums[size++] = val;
Arrays.sort(nums); // 保证是一个排序好的数组，后面只需要比较后一个就行。
} else {
if (val > nums[0]) {
nums[0] = val;
int i = 0 ;
while (k > i) {
if (nums[i] < nums[i+1]) break;
int m = nums[i+1];
nums[i+1] = nums[i];
nums[i] = m;
i++;
}
}
}
return nums[0];
}
}第三种方法：运用小顶堆代替 长度为K的数组 ，判断最小元素
解题思路
通过Java中内置的优先队列，也就是小顶堆（最小值永远在根节点），每次传入数字和根节点比较一下，根据结果，决定是否存入和返回。存入则必须输出根节点，再存入当前值，保证小顶堆最小值 等于 第K大的元素，时间复杂度O(N*logk)。
class KthLargest {
final PriorityQueue<Integer> queue;
final int k ;
public KthLargest(int k, int[] nums) {
this.k = k ;
queue = new PriorityQueue<Integer>();
for (int num : nums) {
add(num);
}
}
public int add(int val) {
if (queue.size() < k) { //保证小顶堆中只有k个元素
queue.offer(val);
} else if (queue.peek() < val) {
queue.poll();
queue.offer(val);
}
return queue.peek();
}
}第一种方法，直接保存数组再排序，实际上浪费时间和空间保存无限增长的数组。
第二种方法，虽然优化了第一种，只保存K个元素的数组，但是每次改变数组又再次排序了，我们知道，数组中的元素是不必排序的，只需要知道第K大元素即可。
第三种方法，只保存K个元素的数组，也只确定第K大元素的位置即可，利用小顶堆只寻找最小值的特性，并没有对整个数组进行排序。
leetcode:239返回滑动窗口内的最大值
题目讲的很明白了，去一个窗口内的最大值，这个窗口我们可以用规定大小数组来代替，后面向数组输入元素，也就是队列，元素先进先出，在队列中进行排序，找到当前队列中最大值，那么也就可以优先队列的概念了，但，这次是要用到大顶堆。
方法一、优先队列（大顶堆）
class Solution {
final PriorityQueue<Integer> queue = new PriorityQueue<>((a,b)->b-a); //比较器改变，使优先队列 从小顶堆改变为大顶堆
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums==null || nums.length<2) return nums;
int[] ret = new int[nums.length-k+1]; //存储输出结果
int i = 0;
for (int num : nums) {
if (queue.size() < k) {
queue.offer(num);
} else {
queue.remove(nums[i++]); //移除窗口外元素
queue.offer(num);
}
if (queue.size() >= k) ret[i] = queue.peek(); //保存窗口中最大元素
}
return ret;
}
}因为使用了优先队列的缘故，这个时间复杂度O(N*logK）
方法二、迭代前K个元素，找出最大值
class Solution2 {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums==null || nums.length<2) return nums; //nums: [] k:0 输出：[0]
int maxIdx = 0;
int max = nums[0];
int[] ret = new int[nums.length-k+1];
for(int i = 0;i<k;i++){ //首先求出前k个的最大值
if(nums[i]>=max){
max = nums[i];
maxIdx =i;
}
}
ret[0]=max;
for(int i = k;i<nums.length;i++){
if(max <=nums[i]){
max = nums[i];
maxIdx = i;
}else if(maxIdx == i-k){ //判断队首下标有没有超出范围，超出了则移除
max = nums[i];
maxIdx=i;
for(int j = i-1;j>i-k;j--){ //迭代前K个元素，找出最大值
if(nums[j]>max){
max = nums[j];
maxIdx =j;
}
}
}
ret[i-k+1]=max;
}
return ret;
}
}腾讯云开发者
