Leetcode076 -- the kth largest number in the array

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 .

Example 1:

Input : [3,2,1,5,6,4] and k = 2
Output : 5
Example  2:

Input : [3,2,3,1,2,4,5,5,6] and k = 4
Output : 4
 

Tips ：

1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104

Ideas ：

The most intuitive solution is to sort the array , Output length-k The number of positions is enough . But there must be unnecessary operations in this way .

  Fast scheduling algorithm can refer to ： Fast and slow pointer to achieve fast row

How to optimize ？

int findKthLargest(vector<int>& nums, int k) {
    quicksort(nums, 0, nums.size() - 1);
    return nums[nums.size() - k];
}

Optimization idea ：

Using the idea of fast platoon , Every round partition Will find an axis value corresponding to the sorted position , When the last position of this axis value is k When , Just output it directly , You don't have to do all the comparisons , The best case is that each axis value is in the median , Two points quick row .

The code is as follows ：

    int findKthLargest(vector<int>& nums, int k) {
        int start = 0, end = nums.size() - 1;
        int index = partition(nums, start, end);
        while(index != nums.size() - k) {
            if (index > nums.size() - k) {
                end = index - 1;
                index = partition(nums, start, end);
            } else if (index < nums.size() - k) {
                start = index + 1;
                index = partition(nums, start, end);
            }
        }

        return nums[index];
    }

    int swap(vector<int>& nums, int left, int right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
        return 0;
    }

    int partition(vector<int>& nums, int start, int end) {
        int index = (start + end) / 2;
        swap(nums, index, end);

        int small = start - 1;
        for (index = start; index < end; index++) {
            if (nums[index] < nums[end]) {
                ++small;
                if (small != index) {
                    swap(nums, small, index);
                }
            }
        }

        ++small;
        swap(nums, small, end);
        return small;
    }