subject ：

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 .

Answer key ：

Line up every round partition You can put the selected pivot Put it in its final ordered position , When a round pivot Put in the second place k Large element location （ Subscript of ordered sequence from small to large n-k It's about ） when , Determine the pivot As a result

pivot The choice of using random numbers can prevent the worst time complexity .

nextInt() usage ：

Will randomly generate an integer , The range of this integer is int The range of types -2^31 ~ 2^31-1, But if nextInt() Add an integer in parentheses a that , The range of randomly generated random numbers becomes [0,a).

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // The first k Big element , That is, the subscript after sorting is n-k The elements of , Use partition Method to determine the subscript n-k Elements 
        int target = nums.length - k;
        int from = 0, to = nums.length - 1;
        while (true) {
            int idx = partition(nums, from, to); // Every time partition return pivot Insertion position 
            if (idx == target) { // If the insertion position is the target position , Find No k Big element 
                return nums[target];
            } else if (idx > target) { // If the insertion position is greater than the target position , The target location search range should be idx On the left 
                to = idx - 1;
            } else { // If the insertion position is less than the target position , The target location search range should be idx On the right 
                from = idx + 1;
            }
        }
    }

    Random rand = new Random();
    // Return single partition determine pivot Where the element is fixed 
    private int partition(int[] nums, int from, int to) {
        int pivotIndex = rand.nextInt(to - from + 1) + from;
        int pivot = nums[from];
        // Random pivot Swap to the head 
        int temp = nums[from];
        nums[from] = pivot;
        nums[pivotIndex] = temp;

        int left = from, right = to;
        while (left < right) {
            while (left < right && nums[right] >= pivot) { // Find the first one from right to left <pivot Of 
                right--;
            }
            if (left < right) {
                nums[left] = nums[right];                
            }
            while (left < right && nums[left] <= pivot) { // Find the first one from left to right >pivot Of 
                left++;
            }
            if (left < right) {
                nums[right] = nums[left];                
            }
        }
        nums[left] = pivot; // Finally, put pivot Put it in left The location of 
        return left;
    }
}

Reference resources ： Power button