5 天前	#295 数据流的中位数	困难	1 次
5 天前	#347 前 K 个高频元素	中等	5 次
5 天前	#215 数组中的第K个最大元素	中等	4 次

备注：

1、前k个高频元素 queue.poll()[0] 这个注意

2、数据流的中位数， 注意放入的时候 ab两个都要放

​ A.add(num);

​ B.add(A.poll());

数组中第k个最大元素

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length-k];
    }
}
思路：
  1、这种题  先排序 （一般排序都是自己选择的）建议快排，一般考察点就是这个
  2、直接返回 倒数第k个

前k个高频元素

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int n : nums){
            map.put(n, map.getOrDefault(n,0)+1);
        }

        PriorityQueue<int[]> queue = new PriorityQueue<>((a,b)->b[1]-a[1]);
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            queue.add(new int[]{entry.getKey(), entry.getValue()});
        }

        int[] res = new int[k];
        for(int i = 0;i<k;i++){
            res[i] = queue.poll()[0];
        }
        return res;
    }
}
思路：
  1、定义map 缓存个数
  2、利用PriorityQueue  放进去
  3、最后弹出来的就是 次数最多的

数据流的中位数

class MedianFinder {
    Queue<Integer> A, B;
    public MedianFinder() {
        A = new PriorityQueue<>(); // 小顶堆，保存较大的一半
        B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
    }
    
    public void addNum(int num) {
        if (A.size() != B.size()) {
            A.add(num);
            B.add(A.poll());
        } else {
            B.add(num);
            A.add(B.poll());
        }
    }
    
    public double findMedian() {
        return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
    }
}

思路：
  1、依然是 PriorityQueue 一个正序  一个反序
  2、最后找中位数 也是判断 奇数跟偶数的