记录面试高频率的（215题）力扣自己的思路

1.先是快速排序，使第一个关键字找到自己的位置，然后前面是小于自己的数值，后面是大于自己的数值

2.然后通过比较关键字的值和待查找的值的大小，小于就在右边的表寻找（left+1），小于就在左边的表找（right-1）

3.循环下去就逐渐缩小可以找到满足条件的值了

class Solution {
    public int findKthLargest(int[] nums, int k) {
   
    int len=nums.length;
    int left=0;
    int right=len-1;

    int target=len-k;

    while(true){
        int index=partition(nums,left,right);//多次循环，直到找到答案
        if(index==target){
            return nums[index];
        }else if(index<target){
            left=index+1;//<,说明在右边
        }else{
            right=index-1;//说明在左边
        }
    }

    }
/**
     * 在数组 nums 的子区间 [left, right] 执行 partition 操作，返回 nums[left] 排序以后应该在的位置
     * 在遍历过程中保持循环不变量的语义
     * 1、[left + 1, j] < nums[left]
     * 2、(j, i] >= nums[left]
     *
     * @param nums
     * @param left
     * @param right
     * @return
     */

    public int partition(int[]nums,int left,int right){
        int pivot=nums[left];
        int j=left;
        for(int i=left+1;i<=right;i++){
            if(nums[i]<pivot){
                j++;
                swap(nums,j,i); // 小于 pivot 的元素都被交换到前面，大的也换到后面去了
            }
        }
        // 在之前遍历的过程中，满足 [left + 1, j] < pivot，并且 (j, i] >= pivot
        swap(nums,j,left);//这是最终位置的那个数字调换和第一个关键字
        // 交换以后 [left, j - 1] < pivot, nums[j] = pivot, [j + 1, right] >= pivot
        return j;//返回这是第一个关键字的最终位置
    }

    private void swap(int[]nums,int index1,int index2){
        int temp=nums[index1];
        nums[index1]=nums[index2];
        nums[index2]=temp;
    
    }
}