数组中的第K个最大元素

两种方法，第一种，使用快排的改进版本。第二种维护一个k大小的最小堆，堆顶是当前k个元素里面最小的。

快速排序的核心是：迭代选中的某个数在其有序列中的下标位置，因此可以每次排序完毕后，查看下是不是符合第k个。

可以改进快速排序算法来解决这个问题：在分解的过程当中，我们会对子数组进行划分，如果划分得到的 q 正好就是我们需要的下标，就直接返回 a[q]；否则，如果 q 比目标下标小，就递归右子区间，否则递归左子区间。这样就可以把原来递归两个区间变成只递归一个区间，提高了时间效率。这就是「快速选择」算法。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        // 第k大 = 第n-k小（0-based）
        return quickSelect(nums, 0, n - 1, n - k);
    }
    public int quickSelect(int[] nums, int l, int r, int k) {
        if (l == r) return nums[l];
        int x = nums[l];
        int i = l, j = r;
        while (i < j) {
            // 先右后左
            while (i < j && nums[j] >= x) j--;
            while (i < j && nums[i] <= x) i++;
            if (i < j) {
                swap(nums, i, j);
            }
        }
        // 基准值归位
        nums[l] = nums[i];
        nums[i] = x;
        if (k == i) {
            return nums[i];
        } else if (k < i) {
            return quickSelect(nums, l, i - 1, k);
        } else {
            return quickSelect(nums, i + 1, r, k);
        }
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

前k个高频元素

堆排序，小根堆。需要重写排序

借助哈希表来建立数字和其出现次数的映射，遍历一遍数组统计元素的频率 维护一个元素数目为 k 的最小堆 每次都将新的元素与堆顶元素（堆中频率最小的元素）进行比较 如果新的元素的频率比堆顶端的元素大，则弹出堆顶端的元素，将新的元素添加进堆中 最终，堆中的 k 个元素即为前 k 个高频元素

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(map.get(nums[i]) == null){
                map.put(nums[i],1);
            }else{
                map.put(nums[i], map.get(nums[i]) + 1);
            }
        }

        // 维护小根堆 频率最低的最顶 需要重写堆的compare
        // 用lambda表达式重写 
        PriorityQueue<Integer> pq = new PriorityQueue<>(
            (a, b) -> map.get(a) - map.get(b)
        );
        for(Integer key : map.keySet()){
            if(pq.size() < k){
                pq.add(key);
            }else if(map.get(key) > map.get(pq.peek())){
                pq.remove();
                pq.add(key);
            }
        }
        int[] res = new int[k];
        for(int i = 0; i < k; i++){
            res[i] = pq.remove();
        }
        return res;
    }
}

数据流的中位数

建一个小顶堆和大顶堆，小顶堆保留较大的那一半，大顶堆保留较小的那一半。设总数N = m+n

• 当 m=n（即 N 为 偶数）：需向 A 添加一个元素。实现方法：将新元素 num 插入至 B ，再将 B 堆顶元素插入至 A 。
• 当 m\=n（即 N 为 奇数）：需向 B 添加一个元素。实现方法：将新元素 num 插入至 A ，再将 A 堆顶元素插入至 B 。

class MedianFinder {
    Queue<Integer> A, B;
    public MedianFinder() {
        A = new PriorityQueue<>(); // 小顶堆，保存较大的一半
        B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
    }
    
    // 规定总数若为奇数个 则A的个数会比B的+1
    public void addNum(int num) {
        if (A.size() != B.size()) {
            // size不相等的话 一定是A比B多一个 向B加一个
            A.offer(num);
            B.offer(A.poll());
        } else {
            // 个数相同的话 先放B里面 再取出B中最大的放A里面 相当于A比B的数目多1
            B.offer(num);
            A.offer(B.poll());
        }
    }
    public double findMedian() {
        return A.size() != B.size()? A.peek(): (A.peek() + B.peek()) / 2.0;
    }
}