堆----1.数组中的第K个最大元素

215. 数组中的第K个最大元素 - 力扣（LeetCode）

/**

        第一大元素--->len - 1

        第二大元素--->len - 2

        .......

        第K大元素---->len - K,则数组中第K个最大元素,转化为寻找排序后第len - K位置的元素

        快速选择算法:

                    快速排序的变种,核心的分区函数一致,在数组中随机选择一个基准 pivot

                    按基准将数组划分为三个部分 小于基准 基准 大于基准,那么此时基准所在的位置就是排序后该在的位置

                变种:

                    在本题中,若划分后基准所在位置恰好是len - k,那么说明基准就是第K个最大元素

                    若基准 < len - K, 则减小范围,在[基准 + 1,right]中重新选择基准,重复上述流程

                    若基准 > len - K, 则减小范围,在[left, 基准 - 1]中重新选择基准,重复上述流程

                    直到找到为止

                分区函数(核心):

                    首先在数组中随机选择一个元素为基准元素,从左右两端同时开始扫描

                    左指针向右遍历,直到遇到第一个>=pivot的元素

                    右指针向左遍历,直到遇到第一个<=pivot的元素

                    交换左右指针的值,交换后,大于基准元素的在右半区,小于基准元素的在左半区,等于基准元素的平均分布在左、右半区

                细节注意:

                    在选择出基准元素后,将其移至数组首位

                    遍历完毕后基准元素与左指针交换位置,将基准元素移动至正确位置

 */

class Solution {
    /**
        第一大元素--->len - 1
        第二大元素--->len - 2
        .......
        第K大元素---->len - K,则数组中第K个最大元素,转化为寻找排序后第len - K位置的元素
        快速选择算法:
                    快速排序的变种,核心的分区函数一致,在数组中随机选择一个基准 pivot
                    按基准将数组划分为三个部分 小于基准 基准 大于基准,那么此时基准所在的位置就是排序后该在的位置
                变种:
                    在本题中,若划分后基准所在位置恰好是len - k,那么说明基准就是第K个最大元素
                    若基准 < len - K, 则减小范围,在[基准 + 1,right]中重新选择基准,重复上述流程
                    若基准 > len - K, 则减小范围,在[left, 基准 - 1]中重新选择基准,重复上述流程
                    直到找到为止
                分区函数(核心):
                    首先在数组中随机选择一个元素为基准元素,从左右两端同时开始扫描
                    左指针向右遍历,直到遇到第一个>=pivot的元素
                    右指针向左遍历,直到遇到第一个<=pivot的元素
                    交换左右指针的值,交换后,大于基准元素的在右半区,小于基准元素的在左半区,等于基准元素的平均分布在左、右半区
                细节注意:
                    在选择出基准元素后,将其移至数组首位
                    遍历完毕后基准元素与左指针交换位置,将基准元素移动至正确位置
    */

    private int[] nums;
    private int target;
    private final Random random = new Random();

    public int findKthLargest(int[] nums, int k) {
        this.nums = nums;
        this.target = nums.length - k;

        quickSelect(0,nums.length - 1);
        return nums[target];
    }

    //快速选择
    private void quickSelect(int left, int right) {
        if(left > right) {
            return;
        }

        int pivotIndex = partition(left, right); //得到第一个有序的位置

        if(pivotIndex == target) { 
            return;
        } else if(pivotIndex < target) {
            quickSelect(pivotIndex + 1, right); //[基准 + 1,right]
        } else {
            quickSelect(left,pivotIndex - 1); //[left, 基准 - 1]
        }
    }

    //分区函数
    private int partition(int left, int right) {
        //生成随机基准
        int pivot = random.nextInt(right - left + 1) + left;
        int pivotValue = nums[pivot];
        swap(left,pivot); //先将基准移至首位

        //双端同时开始扫描
        int le = left + 1;
        int ge = right;
        
        while(true) {
            //左指针向右遍历,直到遇到第一个>=pivot的元素
            while(le <= ge && nums[le] <pivotValue) {
                le++;
            }

             //右指针向左遍历,直到遇到第一个<=pivot的元素
            while(le <= ge && nums[ge] > pivotValue) {
                ge--;
            }

            //遍历结束退出
            if(le >= ge) {
                break;
            }

            //交换两指针的值,进行分区
            swap(le,ge);
            le++;
            ge--;

        }

        //遍历完毕后基准元素与左指针交换位置,将基准元素移动至正确位置
        swap(left,ge);
        return ge;
    }

    private void swap(int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}