问题：给定整数数组 nums和整数k，请返回数组中第k个最大的元素。
请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。
思路：
- 排序
这是最容易想到的思路，首先将数组排序，然后取倒数第k个就是所求。注意Arrays.sort()默认为自然排序，无法对基本数据类型的数据进行自定义排序，但是可以对其包装类Integer类型的数组自定义排序。
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}
- 优先队列
java的优先队列默认实现为小顶堆。将数组中的元素依次入队列，在此过程中，维护一个长度为k的队列，当队列长度大于k时，将堆顶元素（当前队列中最小的元素）出队，这样当整个数组遍历完之后，我们就留下了较大的k个元素，即堆顶为第k大元素。
class Solution {
public int findKthLargest(int[] nums, int k) {
Queue priorityQueue = new PriorityQueue<>();
for(int num: nums){
priorityQueue.offer(num);
if(priorityQueue.size() > k){
priorityQueue.poll();
}
}
return priorityQueue.peek();
}
}
- 快速选择算法
快速选择算法是快速排序算法的优化版本。
快速排序的逻辑是，若要对 nums[l..r] 进行排序，我们先找一个分界点 p，通过交换元素使得 nums[l..r] 都小于等于 nums[p]，且 nums[p+1..r] 都大于 nums[p]，然后递归地去 nums[l..p-1] 和 nums[p+1..r] 中寻找新的分界点，最后整个数组就被排序了。
需要优化的点在这里：每一次快排之后，分界点p的位置会被确定，我们要求的是第k大元素，这个第k大元素在升序后的数组中的位置为nums.length - k。既然我们知道了所求元素的位置，且每一次快排会确定分界点p的位置。那我们可以是用确定位置的分界点p和k作比较，若p < k，则说明第k大元素肯定在区间[p+1, r]，若p > k，则说明第k大元素肯定在区间[l, p - 1]。p == k，则nums[p]即为所求。
class Solution {
public int findKthLargest(int[] nums, int k) {
int l = 0, r = nums.length - 1;
k = nums.length - k;
while(l <= r){
int p = partition(nums, l, r);
if(p < k){
l = p + 1;
} else if(p > k){
r = p - 1;
} else {
return nums[p];
}
}
return -1;
}
private int partition(int[] nums, int l, int r) {
if (l == r) {
return l;
}
int pivot = nums[l];
int i = l, j = r + 1;
while (true){
//保证nums[l...i]都小于分界点pivot
while (nums[++i] < pivot){
if (i == r) {
break;
}
}
//保证nums[j...r]都大于分界点pivot
while (nums[--j] > pivot){
if (j == l) {
break;
}
}
if(i >= j) {
break;
}
//走到这里一定有
//nums[i] > pivot && nums[j] < pivot
//此时需要交换 nums[i] 和 nums[j]，
swap(nums, i, j);
}
//此时i指向右半区间第一个大于pivot的数
//j指向左半区间最后一个小于pivot的数
//所以应该将j与分界点l交换
//这样才满足以nums[pivot]分界点，左半区间都小于它，右半区间都大于它
swap(nums,j,l);
return j;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
整理思路，记录博客，以便复习。若有误，望指正~
