基础算法 - 堆

public class Solution {
    // 递归函数
    private int quickSelect(List<Integer> nums, int k) {
        // 随机选择基准数
        Random rand = new Random();
        int pivot = nums.get(rand.nextInt(nums.size()));
        // 将大于、小于、等于 pivot 的元素划分至 big, small, equal 中
        List<Integer> big = new ArrayList<>();
        List<Integer> equal = new ArrayList<>();  // 可能会有重复的数
        List<Integer> small = new ArrayList<>();
        for (int num : nums) {
            if (num > pivot)
                big.add(num);
            else if (num < pivot)
                small.add(num);
            else
                equal.add(num);
        }
        // 第 k 大元素在 big 中，递归划分
        if (k <= big.size())
            return quickSelect(big, k);
        // 第 k 大元素在 small 中，递归划分
        if (big.size() + equal.size() < k)
            return quickSelect(small, k - big.size() - equal.size());
        // 第 k 大元素在 equal 中，直接返回 pivot
        return pivot;
    }
    
    public int findKthLargest(int[] nums, int k) {
        List<Integer> numList = new ArrayList<>();
        for (int num : nums) {
            numList.add(num);
        }
        return quickSelect(numList, k);
    }
}

public class Solution {
    
        public int findKthLargest(int[] nums, int k) {
        // 题目明确了 nums[i]的范围为 -10000 10000
        int min = -10000;
        int max = 10000;
        int[] cnt = new int[max-min+1];
        // 计数
        for(int i=0;i<nums.length;i++){
            cnt[nums[i]-min]++;
        }
        int idx = 0;
        // 反向遍历，从最大的往前找
        for(int i=max-min;i>=0;i--){
            k -= cnt[i];
            if(k<=0)return i + min;
        }
        return 0;
    }
}

public class Solution {

    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        // 使用一个含有 k 个元素的最小堆，PriorityQueue 底层是动态数组，为了防止数组扩容产生消耗，可以先指定数组的长度
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        for (int i = 0; i < k; i++) {
            minHeap.offer(nums[i]);
        }
        for (int i = k; i < len; i++) {
            // 看一眼，不拿出，因为有可能没有必要替换
            Integer topElement = minHeap.peek();
            // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
            if (nums[i] > topElement) {
                minHeap.poll();  // 移除原来的堆顶
                minHeap.offer(nums[i]);  // 将新元素入堆
            }
        }
        return minHeap.peek();
    }
}

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] res = new int[k];
        // 用字典先记录一下每个数字出现的频率
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int num : nums){
            map.put(num, map.getOrDefault(num,0)+1);
        }
        // 最小堆，定义了lambda表达式，规定其用map中对应的值进行比较
        PriorityQueue<Integer> heap = new PriorityQueue<>(k,(a, b) -> map.get(a) - map.get(b));
        for(Integer key : map.keySet()){
            // 如果堆中元素个数小于k个，那么可以继续加
            if(heap.size()<k){
                heap.offer(key);
            }else{
                // 如果元素个数等于k个了，表明已满，需要进行比较
                Integer peek = heap.peek();
                // 如果当前这个key"够格"入堆，那么入堆
                if(map.get(peek)<map.get(key)){
                    heap.poll();
                    heap.offer(key);
                }
            }
        }
        for(int i=0;i<k;i++){
            res[i] = heap.poll();
        }
        return res;
    }
}

class MedianFinder {

    PriorityQueue<Integer> small;
    PriorityQueue<Integer> big;

    public MedianFinder() {
        small = new PriorityQueue<>();
        big = new PriorityQueue<>((a, b) -> b - a);
    }

    public void addNum(int num) {
        if (small.size() == big.size()) {
            // 当前元素num与small中最小的元素作比较
            // 如果num足够大，可以进入small堆，那么就需要将small堆中最小的元素（堆顶）剔除，放到big堆中，之后将num放入small堆
            if (big.isEmpty() || num < small.peek()) big.offer(num);
            else {
                big.offer(small.poll());
                small.offer(num);
            }
        } else {
            if (num > big.peek()) small.offer(num);
            else {
                small.offer(big.poll());
                big.offer(num);
            }
        }
    }

    public double findMedian() {
        if (small.size() != big.size() && !big.isEmpty()) {
            return (double) big.peek();
        } else if (small.size() == big.size() && !small.isEmpty()) {
            return (double) (small.peek() + big.peek()) / 2;
        }
        return -1;
    }
}