Leetcode215 the kth largest element (derivation of quick sort partition function)

1. problem

Find the second in the array k The biggest element ： Given an array of integers nums And integer k, Please return the... In the array k The biggest element . Please note that , What you need to look for is the number after array sorting k The biggest element , Not the first. k A different element .

2. Methods to analyze

      eg: Example 2 After ordering ：122334556,k=4, Here's number k(4) The big element refers to the fourth element from the maximum to the decimal , The output 4【 That is, find the penultimate after sorting k Elements 】, Instead of outputting the fourth different element from big to small 3.

1） Sort （nlogN）

      take nums Array sorting , take arr.length-k The element corresponding to this index can .

put questions to ： If time complexity is required now <nlogn Well ？

2） Use priority queues （nlogK）

      Take the big and use the small , First establish k The smallest heap of elements , Scan the set , Just saved before k The biggest element , At this point, take out the top element .（ The top element is the first k Big elements ）

3） Use the partition function of fast row （O(n)）

      Require a set of The first k Big element , It happens to be The... After sorting the set n-k An index The value of the location , The partition function returns the last index after sorting ？ Every time an element is delimited between partitions, the position of the element is determined and the corresponding index position of the element is returned , If this index is exactly equal to n-k Location index , Then solve the problem directly .

3. Code implementation

Code implementation based on fast sorting partition function

public class Num251_FindKLargest {
    private  Random random=new Random();
    public  int findKthLargest(int[] nums, int k) {
        // Use the quick row partition function , When partitioning, find the element index after partitioning and nums.length-k Values with the same index , This value is the value to be found 
        // Returns the largest element 
        //nums.length-k: Last but not least k A place ; The first k The largest element is the penultimate element after sorting nums.length-k The elements of 
        if(k>nums.length){
            throw new NoSuchElementException("illegal k,error");
        }
        return quickSortSelect(nums,0,nums.length-1,nums.length-k);
    }
    // Choose whether to sort ,== You don't need to sort the situation, just return the value , This question is mainly about evaluation 
    private  int quickSortSelect(int[] nums, int l, int r, int index) {
        // If index It is the same as the index of the returned demarcation point , There is no need to continue to line up 
        int p=partition(nums,l,r);// Return the demarcation point index 
        if(p==index){
            return nums[p];
        }
        // The sorted partition point index is not equal to the penultimate k An index index
        // Partition point subscript <index, Recursive right interval ,>index Recursive left interval 
        return p<index?quickSortSelect(nums,p+1,r,index):quickSortSelect(nums,l,p-1,index);
    }
    //nums[l...r] Sort 
    private  int partition(int[] nums, int l, int r) {
        int randomIndex=random.nextInt(r-l+1)+l;
        swap(nums,l,randomIndex);
        int v=nums[l];
        //nums[l+1...j]<v
        //nums[j+1...i)>=v
        int j=l;
        //i Is currently traversing the element 
        for (int i = l+1; i <= r ; i++) {
            if(nums[i]<v){
                swap(nums,i,j+1);
                j++;
            }//else It only needs i++, The conditions have been written 
        }
        // After the cycle is completed, the partition is divided , In exchange for l And j Index position element （j Location is <v Last element of ）
        swap(nums,l,j);
        return j;
    }

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