力扣215 数组中第k大的数

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

本题主要考察各种排序算法，要求时间O（n），严格意义上说只有计数排序满足条件。
数据结构：数组
算法：由于数组最大范围是10000，存在负数。申请一个20000的数组，将原数组的数作为新数组下标（+10000因为存在负数），然后从后往前减，求出第K大的数。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        //用20000个是因为它可能出现负值
        int[] buckets = new int[20001];
        for (int i = 0; i < nums.length; i++) {
            buckets[nums[i] + 10000]++;
        }
        for (int i = 20000; i >= 0; i--) {
            //bukets[i]表示num的数量
            k = k - buckets[i];
            //出现小于0是因为可能重复
            if (k <= 0) {
                return i - 10000;
            }
        }
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18