import java.util.*;
public class Solution {
public int findKth(int[] a, int n, int K) {
// write code here
return minHead(a, n ,K);
}
private int minHead(int[] a, int n, int K){
//用优先队列，生成最小堆，java默认是对顶元素最小，c 默认最大
PriorityQueue<Integer> minHead = new PriorityQueue<>();
for(int i = 0; i< K ; i ){
minHead.offer(a[i]);//遍历k 个元素入堆。堆顶元素最小
}
//优先队列
//由于找第 K 大元素，其实就是整个数组排序以后后半部分最小的那个元素。因此，我们可以维护一个有 K 个元素的最小heap
// 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去(堆这种数据具有内部shiftup , shiftdown 功能，自己维持最小堆。Java默认的是最小堆。)
for(int j = K ; j < n ; j ){
if(a[j] >= minHead.peek()){//遍历数组其他元素，如果比堆顶元素大的，继续入堆。
minHead.poll();
minHead.offer(a[j]);
}else{
continue;
}
}
return minHead.peek(); //遍历结束数组，最后堆顶就是第k 大的那个元素
}
}
/**
* topK 问题的第二种解法
* 时间复杂度：O(NlogK)，遍历数据 O(N)，堆内元素调整 O(K)；
* 空间复杂度：O(K)。
*/
//优先队列
//由于找第 K 大元素，其实就是整个数组排序以后后半部分最小的那个元素。因此，我们可以维护一个有 K 个元素的最小heap
// 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去(堆这种数据具有内部shiftup , shiftdown 功能，自己维持最小堆。Java默认的是最小堆。)
解法二： 快排
package testTopK;
public class L215 {
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.findKthLargest(new int[]{1,3,45,2,3,4,2,34}, 5));//测试用例
}
}
class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
int targetIndex = len - k;//第k 大元素的下. 因为第k 大是从后面开始数的
int low = 0, high = len - 1;
while (true) {
int i = quickSort(nums, low, high);
// 1、当 partition 函数返回的下标 i=len-k，则 arr[i] 就是我们要求的第K大元素
// 2、当 partition 函数返回的下标 i<len-k，那么说明第K大元素在下标 i 的右边，我们继续分区在 arr[i 1, len-1] 区间内查找：partition(arr, i 1, len-1)
// 3、当 partition 函数返回的下标 i>len-k，那么说明第K大元素在下标 i 的左边，我们继续分区在 arr[0, i-1] 区间内查找：partition(arr, 0, i-1)
//
// 该方法的时间复杂度是O(n)
if (i == targetIndex) {
return nums[i];//最后返回这个
} else if (i < targetIndex) {
low = i 1;
} else {
high = i - 1;
}
}
}
/**
* 分区函数，将 nums[start] 作为 flag锚点
* 一左，一右，两个指针，遍历数组，左边找比第一个数大的，右边找比flag小的，{左大右小}找到了就立马交换{左小右大}
* 直到遍历指针相等，left == right , 这时候 将nums[i]和 flag 进行交换，返回下标 i，就是分区点的下标。
*/
public int quickSort(int[] nums, int start, int end){ //返回int
// if(start >= end){
// return;
// }不需要递归
int left = start;
int right = end;
int flag = nums[start];
while(left < right){
while(left < right && nums[right] >= nums[start]){
right--;// >=
}
while(left < right && nums[left] <= nums[start]){
left ;
}
int temp = nums[right];
nums[right] = nums[left];
nums[left] = temp;
}
//left == right
nums[start] = nums[right];//nums[start] = nums[left];//交换锚点元素
nums[right] = flag;
return left;//return right;//返回下标。
// quickSort(nums, start, left-1);//这是递归，原来的快排的代码，直到排序完成，这题不需要
// quickSort(nums,left 1,end);
}
}
大家加油：P
,
