数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4解题思路 思路一
求数组中第k大的元素，常规思路肯定是先排序，然后再取第k大的元素。采用java官方自带的Arrays.sort()方法，该方法底层在jdk1.8以后采用的是双轴快排，时间复杂度一般能保持在O(NlogN)，但面试中碰到这种题时肯定不能用，不然就回家等通知了。
思路二快排虽然快，但是在遇到特殊的测试用例（数组完全有序或完全逆序）时，递归树会退化成链表。在每次快排前定义基准值时，采用随机数策略，防止切分数组时出现极端情况，导致时间复杂度为O(N^2)。快排模板最好能背来，面试手撕代码时很有用。
思路三在选基准值时，随机交换数组中下标为0的元素和它后面的任意元素的位置。
采用堆排序，构建大顶堆，排序一次能得到最大值，那排序第k次得到的必然是该数组中第k大的元素。
代码实现直接调用API：
class Solution {
// 数组元素可重复，排序后找第K个最大的，排序后，第k大的元素在nums[nums.length - k]
public int findKthLargest(int[] nums, int k) {
// 调API法，不推荐
Arrays.sort(nums);
return nums[nums.length - k];
}
}
快速排序：
public class LC_215 {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
int left = 0, right = len - 1;
// 第 k 大元素的下标是 len - k
int target = len - k;
while(true) {
int index = partition(nums, left, right);
if(index == target) {
return nums[index];
} else if (index > target) {
right = index - 1;
} else {
left = index + 1;
}
}
}
public int partition(int[] nums, int left, int right) {
// 在区间随机选择一个元素作为基准值
// 会随机生成一个整数，这个整数的范围就是int类型的范围-2^31 ~ 2^31-1,
// 但是如果在nextInt()括号中加入一个整数a，那么，这个随机生成的随机数范围就变成[0,a)
int randomIndex = new Random().nextInt(right - left + 1) + left;
swap(nums, left, randomIndex);
int pivot = nums[left];
int i = left, j = right;
while(i < j) {
while(i < j && nums[j] >= pivot) j--;
while(i < j && nums[i] <= pivot) i++;
if(i < j)
swap(nums, i, j);
}
// 循环结束，把基准数移到i下标，基准值位置确定
swap(nums, i, left);
return i;
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
堆排序：
public class LC_215_2 {
public int findKthLargest(int[] nums, int k) {
int heapSize = nums.length;
// 构建大顶堆（建立的同时已调整成大顶堆）
buildMaxHeap(nums, heapSize);
// 上面建堆完成，nums[0]为最大元素
// 逐个删除堆顶元素，直到删除了 k-1 个
for(int i = nums.length - 1; i >= nums.length - k + 1; i--) {
// 先把堆的最后一个元素与堆顶元素交换，交换后，堆被破坏，需要调整结点满足堆
swap(nums, 0, i);
// 相当于删除堆顶元素（最大值），
heapSize--;
maxHeapify(nums, 0, heapSize);
}
return nums[0];
}
// 建立大顶堆
public void buildMaxHeap(int[] arr, int heapSize) {
// 从最后一个非叶子节点开始调整每一个结点的子树
for(int i = heapSize >> 1; i >= 0; i--){
maxHeapify(arr, i, heapSize);
}
}
// 判断当前结点（下标为i）是否需要调整
public void maxHeapify(int[] arr, int i, int heapSize) {
// 当前结点i的左右孩子的下标
int left = i * 2 + 1, right = i * 2 + 2;
// max暂存当前根左右三个结点的最大值
int max = i;
// 如果左孩子在数组内，且比当前结点大，最大值暂存左孩子
if(left < heapSize && arr[left] > arr[max]) max = left;
// 如果右孩子在数组内，且比当前最大值还要大，最大值暂存右孩子
if(right < heapSize && arr[right] > arr[max]) max = right;
// 上面两个if完了后，如果最大值不是当前结点i，则交换当前结点和当前max所指向的孩子结点
if(max != i) {
swap(arr, i, max);
// 交换了当前结点和孩子结点，因此可能下面的子树堆性质被破坏，所以对孩子的子树进行调整
// 那么当前结点则为max了，进行递归
maxHeapify(arr, max, heapSize);
}
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
