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;
    }
}