hot100之堆

虽然更多用的是桶

数组中的第k个最大元素(215)

桶排序

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int[] buckets = new int[200001];
        for (int i = 0; i < nums.length; i++){
            buckets[nums[i]+10000]++;
        }
        for (int i = 20000; i >= 0; i--){
            k -= buckets[i];
            if (k <= 0){
                return i - 10000; 
            }
        }
        return 0;
    }
}

选择排序

class Solution {
    public int findKthLargest(int[] nums, int k) {
        List<Integer> numList = new ArrayList<>();
        for (int num : nums){
            numList.add(num);
        }
        return quickSelect(numList, k); 
    }

    private int quickSelect(List<Integer> nums, int k){
        Random rand = new Random();
        int midd = nums.get(rand.nextInt(nums.size()));

        List<Integer> big = new ArrayList<>();
        List<Integer> sma = new ArrayList<>();

        for (int num : nums){
            if (num > midd){
                big.add(num);
            }
            else if (num < midd){
                sma.add(num);
            }
        }

        if (k <= big.size()) return quickSelect(big, k);
        else if (nums.size() < k + sma.size()) return quickSelect(sma, k  + sma.size() - nums.size());
        return midd;
    }
}

• 分析

桶排序

nums[i] 只有 10⁴, 便毅然决然的打表了 ???? , 很坏啊击败了90%

选择排序

随机选择数组中的一个数作为中轴, 通过比较k落在中轴左端还是右端, 进一步缩小范围

前k个高频元素

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int n = nums.length;
        Map<Integer, Integer> num_buckets = new HashMap<>();
        for (int num : nums){
            num_buckets.merge(num, 1, Integer::sum);
        }
        int max_nums = Collections.max(num_buckets.values());

        List<Integer>[] freq_buckets = new ArrayList[max_nums+1];
        Arrays.setAll(freq_buckets, i -> new ArrayList<>());
        for (Map.Entry<Integer, Integer> entry : num_buckets.entrySet){
            freq_buckets[entry.getValue()].add(entry.getKey());
        }

        int[] res = new int[k];
        int count = 0;
        for (int i = max_nums; count < k && i >= 0; i--){
            for (int num : freq_buckets[i]) res[count++] = num;
        }

        return res; 
    }
}

• 分析

以每个<整数>分桶, 再以<频率>对整数分桶

选择 hash而不是 int[] → 元素重复数量大

数据流的中位数(295)

class MedianFinder {
    private PriorityQueue<Integer> lef = new PriorityQueue<>((a,b) -> b-a); //大堆
    private PriorityQueue<Integer> rig = new PriorityQueue<>();    //小堆  

    public MedianFinder() {  
    }
    
    public void addNum(int num) {
        if(lef.size() == rig.size()){
            rig.offer(num);
            lef.offer(rig.poll());        
        }else{
            lef.offer(num);
            rig.offer(lef.poll());
        }
    }
    
    public double findMedian() {
        if (lef.size() != rig.size()){
            return lef.peek();
        }
        return (lef.peek() + rig.peek()) / 2.0;
    }
}

• 分析

排序部分 - > addNum先在对端排序, 取出对端的 最小\最大 值

取中位数部分- > 当总数为奇数时, 以lef.peek()作为中位数, 需要保持 lef.size() ≥ rig.size()