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

给定整数数组 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

提示：

# 思路

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

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

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

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

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

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

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

特别地，我们应随机选择基准元素，使得快速算法算法的时间代价的期望为 $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)$

参考：