雖然更多用的是桶

數組中的第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()