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

215. Kth Largest Element in an Array

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

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

你必须设计并实现时间复杂度为 $O(n)$ 的算法解决此问题。

示例 1：

输入：nums = [3,2,1,5,6,4], k = 2
输出：5

示例 2：

输入：nums = [3,2,3,1,2,4,5,5,6], k = 4
输出：4

提示：

• $1 \le$ k $\le$ nums.length $\le 10^5$
• $-10^4 \le$ nums[i] $\le 10^4$

# 思路

数组第 k 个最大元素，即，数组降序排序后的第 k 个元素（或者，升序排序后的倒数第 k 个元素）

对整个数组排序的时间复杂度至少为 $O(n \log{n})$，其中 $n$ 是数组 nums 的长度

有一种基于快速排序的算法，可以确定某一个元素在排序以后的位置，即，快速选择 算法

# Method 1: 基于快速排序的选择方法

算法思路：（以 寻找降序排序后的第 k 个元素 为例）

快速排序的划分操作：从区间 [left, right] 中选择任意一个元素作为基准，调整子数组，使得位置 p 左侧的元素都大于等于基准元素，位置 p 右侧的元素都小于基准元素，于是，基准元素的最终位置就是 p

即，nums [p] 左侧元素全都大于等于 nums [p]，nums [q] 右侧元素全都小于 nums [p]，于是，nums [p] 就是第 p + 1 个最大元素（数组索引从 0 开始）

因此，可按如下方案求解该问题：

• 如果某次划分的 p 为 k - 1 时，即找到了第 k 个最大元素，可直接返回 nums [p]

• 如果 p 小于 k - 1，则需要查找值更小的元素，即，继续划分 p 右侧的子区间

• 如果 p 大于 k - 1，则需要查找值更大的元素，即，继续划分 p 左侧的子区间

特别地，我们应随机选择基准元素，使得快速算法算法的时间代价的期望为 $O(n)$

代码实现：

// 划分子序列
int partition(vector<int>& nums, int left, int right) { // 随机选择基准，以该基准作为分界线
    int x = left + rand() % (right - left + 1); // 随机生成一个位于区间 [left, right] 内的数
    int pivot = nums[x];        // 划分子序列的基准
    swap(nums[x], nums[right]); // 将基准移至最右侧
    int pos = left - 1;         // 分界线 pos 及其左边的元素一定大于等于 pivot
    for (int i = left; i < right; ++i) { // 划分子序列
        if (nums[i] >= pivot)
            swap(nums[++pos], nums[i]);
    }
    swap(nums[++pos], nums[right]); // 将 pivot 放到分界线位置
    return pos; // 分界线
}

// 快速选择
int quickSelect(vector<int>& nums, int left, int right, int index) { // 寻找降序排列后下标为 index 的元素
    while (true) { // 为降低空间复杂度，这里采用 while 循环，而不采用递归
        int pos = partition(nums, left, right); // nums[pos] 为第 pos + 1 个最大元素（数组索引从 0 开始）
        if (pos == index)     // 寻找到目标下标，该位置元素值即为第 k 个最大元素
            return nums[pos];
        else if (pos < index) // 分界线在目标下标左侧
            left = pos + 1;
        else                  // 分界线在目标下标右侧
            right = pos - 1;
    }
}

int findKthLargest(vector<int>& nums, int k) {
    srand(time(0));
    return quickSelect(nums, 0, nums.size() - 1, k - 1);
}

时间复杂度：$O(n)$，其中 $n$ 是数组 nums 的长度

空间复杂度：$O(1)$

参考：

• leetcode-solution
• liweiwei1419