力扣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;}
}