215. 数组中的第K个最大元素 ●●

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

通过数组下标到堆结构的映射，构建大根堆，经过 k - 1 次交换调整后就能确定第 k 个最大值。

堆排序见：C++ 数据结构与算法 （十一）（排序算法）

时间复杂度： O ( n log ⁡ n ) O(n log n) O(nlogn)，建堆的时间代价是 O ( n log ⁡ n ) O(n log n) O(nlogn)，迭代交换的总代价是 O ( k log ⁡ n ) O(k log n) O(klogn)， k < n k 空间复杂度： O ( 1 ) O(1) O(1)

class Solution {
public:
    void heapAdjust(vector& nums, int root, int n){    // 向下调整为大根堆
        int child = 2 * root + 1;
        while(child < n){
            if(child + 1 < n && nums[child] < nums[child + 1]) ++child;
            if(nums[root] >= nums[child]) break;
            swap(nums[root], nums[child]);
            root = child;
            child = 2 * root + 1;
        }
    }
   
    int findKthLargest(vector& nums, int k) {
        int n = nums.size();
        for(int i = n / 2 - 1; i >= 0; --i){
            heapAdjust(nums, i, n);
        }
        // 迭代 k 次，返回nums[n-k]
        for(int i = 0; i < k; ++i){
            swap(nums[0], nums[n-1-i]);
            heapAdjust(nums, 0, n-1-i);
        }
        return nums[n-k];	// 或者 迭代 k-1 次，返回堆顶nums[0]
    }
};

借鉴快排的思路，不断随机选择基准元素，看进行交换分界(partition)之后，该元素是不是在 n - k 的位置；否则递归其左边或右边查找指定元素（根据当前交换索引与 n - k 的大小来快速选择下一个查找区间）。

快速排序的性能和「划分」出的子数组的长度密切相关。直观地理解如果每次规模为 n 的问题我们都划分成 1 和 n−1，每次递归的时候又向 n−1 的集合中递归，这种情况是最坏的，时间代价是 O ( n 2 ) O(n ^ 2) O(n2)。我们可以引入随机化来加速这个过程，它的时间代价的期望是 O(n)。

随机初始化 pivot 元素，可以在循环一开始的时候，随机交换第 1 个元素与它后面的任意 1 个元素的位置。

• 时间复杂度： O ( N ) O(N) O(N)，这里 N 是数组的长度，证明过程可以参考「《算法导论》9.2：期望为线性的选择算法」。
  O(以n为首项，1/2为等比数列q的等比数列的和) = O(n)
• 空间复杂度： O ( l o g N ) O(logN) O(logN)，递归调用栈

class Solution {
public:
    void quickFind(vector & nums, int left, int right, int k){
        if(left >= right) return;
        int randIndex = rand() % (right - left + 1) + left; // 随机选取一个索引，与left进行替换，作为划分基准
        swap(nums[randIndex], nums[left]);
        int pivot = left;           // 划分基准
        int changePos = pivot;      // 交换索引
        for(int i = pivot + 1; i <= right; ++i){    // 比nums[pivot]小的全部移到紧贴 pivot
            if(nums[i] < nums[pivot]){
                ++changePos;
                swap(nums[i], nums[changePos]);    
            }
        }
        swap(nums[pivot], nums[changePos]);         // 移动nums[pivot]，形成左右分界
        if(changePos == nums.size() - k) return;    // 找到第k大的元素，返回
        if(changePos < nums.size() - k){            // 第k大的元素在右边
            quickFind(nums, changePos+1, right, k);
        }else{                                      // 第k大的元素在左边
            quickFind(nums, left, changePos-1, k);  
        }    
    }

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

• 使用非递归的方法，循环中不断更新区间边界值，优化空间复杂度 O ( 1 ) O(1) O(1)

class Solution {
public:
    int findKthLargest(vector& nums, int k) {
        int left = 0;
        int right = nums.size() - 1;
        while(1){
            int randIndex = rand() % (right - left + 1) + left; // 随机选取一个索引，与left进行替换，作为划分基准
            swap(nums[randIndex], nums[left]);
            int pivot = left;           // 划分基准
            int changePos = pivot;      // 交换索引
            for(int i = pivot + 1; i <= right; ++i){    // 比nums[pivot]小的全部移到紧贴 pivot
                if(nums[i] < nums[pivot]){
                    ++changePos;
                    swap(nums[i], nums[changePos]);    
                }
            }
            swap(nums[pivot], nums[changePos]);         // 移动nums[pivot]，形成左右分界
            if(changePos == nums.size() - k) return nums[nums.size()-k];    // 找到第k大的元素，返回
            if(changePos < nums.size() - k){            // 第k大的元素在右边
                left = changePos + 1; 
            }else{                                      // 第k大的元素在左边
                right = changePos - 1;  
            }    
        }
        return nums[0];
    }
};