一、题目描述
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示：
1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104
二、思路讲解
2.1 方法一：暴力
首先很容易想到将数组排序，然后找到第k大的数字。
public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length - k]; }
时间复杂度： O(NlogN)
空间复杂度： O(1)
虽然可以通过，但是快速排序的时间复杂度达到了NlogN。我们还需要降低时间复杂度。
2.2 方法二：快速选择
根据快速排序的知识我们可以知道，每次partition算法会将所选的基准数（记为target）放到正确的位置，而我们其实只需要知道第k大的位置上的数是什么，而不需要关心其他位置是否有序。那么我们可以根据基准数的位置来判断，假如k在target的左边，那么我们只需要递归target左边即可，而不需要关心target右边是否有序；反之，如果k在target右边，我们只需要递归右边。
class Solution { public int findKthLargest(int[] nums, int k) { return quickSelect(nums, 0, nums.length-1, nums.length-k); } /** partition算法 */ int partition(int []nums, int i, int j) { int target = nums[i]; while(i<j) { while(i<j && nums[j]>=target) { j--; } nums[i] = nums[j]; while(i<j && nums[i]<=target) { i++; } nums[j] = nums[i]; } nums[i] = target; return i; } /** 快速选择算法 */ int quickSelect(int []nums, int i, int j, int index) { if(i>=j) { return nums[i]; } int k = partition(nums, i, j); if(k == index) { return nums[k]; } else if(k < index) { //只递归右半边 return quickSelect(nums, k+1, j, index); } else { //只递归左半边 return quickSelect(nums, i, k-1, index); } } }
时间复杂度： O(N)
空间复杂度： O(logN) 递归使用栈空间的空间代价的期望为 O(logn)
2.3 方法三：堆排序
了解堆排序的朋友们应该可以想到，构建一次大顶堆，堆顶元素就是数组中最大的数，构建第二次大顶堆，堆顶元素就是第二大的数……那么，我们构建k次大顶堆，堆顶元素就是第k大的数了。
class Solution { public int findKthLargest(int[] nums, int k) { return heapSort(nums, k); } int heapSort(int []nums, int k) { for (int i = nums.length/2-1; i >= 0; i--) { adjustHeap(nums, i, nums.length); } //操作k-1次，即可找到第k大的元素 for (int i=nums.length-1; i>nums.length-k-1; i--) { int temp = nums[i]; nums[i] = nums[0]; nums[0] = temp; adjustHeap(nums, 0, i); } return nums[nums.length-k]; } void adjustHeap(int []nums, int i, int length) { int temp = nums[i]; for (int k=2*i+1; k<length; k=2*k+1) { if ((k+1)<length && nums[k]<nums[k+1]) { k++; } if (nums[k]>temp) { nums[i] = nums[k]; i = k; } else { break; } } nums[i] = temp; } }
2.4 方法四：计数排序
题目中只要求时间，没有要求空间，且数字的范围不算很大，那就很适合计数排序了。思想很简单，就不过多介绍了。
class Solution { public int findKthLargest(int[] nums, int k) { //考虑负数 int []count = new int[20001]; for(int num : nums) { count[num+10000]++; } for(int i=count.length-1; i>=0; i--) { k -= count[i]; if(k<=0) { return i-10000; } } return -1; } }
时间复杂度： O(N)
空间复杂度： O(N)
