数组中的第K个最大元素
https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
思路：
通过快速排序的思想，每次选取一个基准点，完成划分使得基准点左侧元素都小于等于基准点，右侧元素都大于等于基准点，这一步和快排思路是一样的，都是通过交换。获取基准点的位置后，判断是不是需要的第K大元素，如果该元素比第K大元素大，那就在基准点后面的范围内继续递归搜索，如果该元素比第K大元素小，那就在基准点前面的范围内搜索。
比较重要的一点是选取基准元素时，进行随机选取，可以加速递归的过程。
class Solution {
public int findKthLargest(int[] nums, int k) {
return findKthLargest(nums, 0, nums.length-1, k);
}
public int findKthLargest(int[] nums, int left, int right ,int k){
int index = randomFindPartition(nums, left, right);
if(index == nums.length-k){
return nums[index];
}
else if(index > nums.length-k){
return findKthLargest(nums, left, index-1, k);
}
else{
return findKthLargest(nums, index+1, right, k);
}
}
//随机选取一个点，作为基准点，移动交换后返回其索引位置
public int randomFindPartition(int[] nums, int left ,int right){
//当left==right时，区间中只有一个数，直接返回
if(left >= right){return left;}
int randomIndex = new Random().nextInt(right-left)+left;
swap(nums, left, randomIndex);
int i = left;
int j = right;
int flag = nums[left];
while(i<j){
while(nums[j] >= flag && i<j){j--;}
while(nums[i] <= flag && i<j){i++;}
swap(nums, i ,j);
}
swap(nums, left, j);
return j;
}
public void swap(int nums[], int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
