215 - Kth Largest Element In An Array

#medium

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

You must solve it in O(n) time complexity.

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

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

https://www.youtube.com/watch?v=zOmIKYKpzB4

快速排序:

1. 選一個當pivot，swap到適合的位置，
2. 我們要一個從大到小的數列，左邊數要比pivot大，右邊要比pivot小，直到兩邊皆滿足，才swap

lass Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // min-heap方法，第k個最大值 = minheap長度為k最小的值
        // quicksort
        int left = 0;
        int right = nums.size() - 1;
        while ( true ) {
            int pos = getPosition( nums, left, right );
            if ( pos + 1 == k ) return nums[pos];
            else if ( pos + 1 > k ) right = pos - 1; //往左邊區間找
            else left = pos + 1; // 往右邊區間找
        }
    }

    int getPosition( vector<int> & nums, int left, int right ) {
        int pivot = nums[left];
        int l = left + 1;
        int r = right;
        // pivot 左邊的值都大於它，右邊的值皆小於它
        // 要使用 <= 否則[2,1]這種情況會報錯
        while ( l <= r ) {
            if ( nums[l] < pivot && nums[r] > pivot ) {
                swap( nums[l], nums[r] );
                l++;
                r--;
            } 

            if ( nums[l] >= pivot ) l++;
            if ( nums[r] <= pivot ) r--;
        }

        swap( nums[left], nums[r] ); // 交換pivot到right的位置
        return r;
    }



};