Quick Select

和他的兄弟Quick Sort一样同为Tony Hoare发明，通过不断二分达到寻找Kth smallest/largest的效果
与Quick Sort不同的是，因为只是Select，所以每次二分后只需要顾及满足条件的一边

    //time: O(N), worst case O(N^2)   space: O(1)
    public int findKthLargestByQuickSelect(int[] nums, int k) {
        return quickselect(nums, 0, nums.length-1, k);
    }
    
    public int quickselect(int nums[], int left, int right, int k_largest) {
        if (left == right) {
            //only one number
            return nums[left];
        }
        //choose the right end as the pivot
        //in this case, actually not need the pivot_index parameter, keep it to make the function formal
        //pivot_index is useful when we randomly select the pivot
        int pivot = partition(nums, left, right, right);
        if (right-pivot+1<k_largest) {
            //pivot is larger than the Kth largest, select again on the left
            return quickselect(nums, left, pivot-1, k_largest-(right-pivot+1));
        } else if (right-pivot+1>k_largest) {
            //pivot is smaller than the Kth largest, select again on the right
            return quickselect(nums, pivot+1, right, k_largest);
        } else {
            //pivot is the Kth largest, return the pivot
            return nums[pivot];
        }
    }
    
    public int partition(int nums[], int left, int right, int pivot_index) {
        int pivot = nums[pivot_index];
        //swap pivot to the end
        nums[pivot_index] = nums[right];
        nums[right] = pivot;
        //go through and split the array to two parts
        pivot_index = right;
        for(int i=0; i<pivot_index; i++) {
            if (nums[i]>pivot) {
                //swap the number with the pivot_index pointer
                pivot_index--;
                int large = nums[i];
                nums[i] = nums[pivot_index];
                nums[pivot_index] = large;
                i--;
            }
        }
        nums[right] = nums[pivot_index];
        nums[pivot_index] = pivot;
        return pivot_index;
    }

相关练习

Leetcode CN 215 - 数据中的第K个最大元素