package arrays;

import java.util.PriorityQueue;
import java.util.Queue;

/**题目:数组中第k大的元素
 * @Author Gavin
 * @date 2022年01月03日 11:41
 */
public class array_12 {
 /**
 * 第一种方法:
 * 先对数组进行排序,然后去k-1下标的值
 * Time:O(n*log(n))
 */
 /**
 * 第二种方法:
 * 使用一个topk的堆
 * Time:O(n*log(k)) Space:O(k)
 */
 /**
 * 第三种方法(值得学习):
 * 使用一种快速排序的思想
 *
 * 注意,这种方法如果在数组有序的情况下时间复杂度较高,可能为O(n^2)
 *
 * 一般多用于无序的数组,这样时间复杂度可以缩短为O(n)
 */
 public int solution1(int[] nums,int k){
 Queue<Integer> minHeap=new PriorityQueue<>();
 for(int num:nums){
 if(minHeap.size()<k){
 minHeap.add(num);
 }else if(num>minHeap.peek()){
 minHeap.poll();
 minHeap.add(num);
 }
 }
 return minHeap.peek();
 }
 //Time:O(n) || O(n^2) Space:O(1)
 public int solution(int[] nums ,int k){
 int low=0,high=nums.length-1;
 while (low<=high){
 //返回快速排序的一个下标
 int p=partition(nums,low,high);
 //如果这个下标等于k-1说明刚好在第k大的位置上
 //快排序之后k左边的元素都小于k,所以只需要判断返回的下标值k-1是不是和
 //p想等,想等的话就返回p就行,因为p左边的元素都是大于p的,p就是第k大的数
 //因为返回的下标是从0开始的,所以需要判断p和k-1的大小
 if(p==k-1)return nums[p];
 //如果返回的下标大于了k-1,说明第k大的元素就在左边去找,否则就在右边去找,
 else if(p>k-1)high=p-1;
 else low=p+1;
 }
 return -1;
 }

 /**
 * 快速排序:
 * 把大于某个元素的值放到左边,小于的放到右边
 * 思想,low左边的元素都比low大,右边的都比low小
 */
 int partition(int[] nums,int low,int high){
 int pivot=nums[low],i=low,j=high;
 while (i<j){
 while (i<j&&nums[j]<pivot)--j;
 //如果遇到右边的元素大于了pivot,就交换到左边来
 if(i<j)swap(nums,i,j);

 while (i<j&&nums[i]>=pivot)++i;
 //如果遇到左边的元素小于pivot,就交换到右边
 if(i<j)swap(nums,i,j);
 }
 return i;
 }
 void swap(int[] nums,int i,int j){
 int tmp=nums[j];
 nums[j]=nums[i];
 nums[i]=tmp;
 }
}