hot100之堆，

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⁴, 便毅然决然的打表了