1. 题目
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
2. 思路
- 针对这个题目，我们首先想到的就是先用排序算法对数据从大到小进行排序，然后直接返回降序后的第 K 个元素即可。
另外，我们也可以借鉴快速排序的思想。每次选取一个 pivot，将大于 pivot 的数放在 pivot 左边，将小于 pivot 的数放在 pivot 右边。
-
这时候，如果 pivot 正好是第 K 个数据，则 pivot 就是数组中的第 K 个最大元素。
1 -
如果 pivot 所在的位置小于 K ，则说明数组中的第 K 个最大元素位于 pivot 的右边。此时，假设 pivot 的位置为 which_max，which_max 是几就代表 pivot 是数组中的第几个最大元素。这时候，我们再从 pivot 右边的数据中找到第 (K-which_max) 个最大元素即可。
2 -
如果 pivot 所在的位置大于 K ，则说明数组中的第 K 个最大元素位于 pivot 的左边。这时候，pivot 左边的数据全部大于 pivot，我们继续从 pivot 左边的数据中找第 K 个最大元素即可。
3 而其中的快速排序算法实现可以有两种思想，具体可参考此处。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
return quick_sort(nums, 0, nums.size()-1, k);
}
// 第一种快排思想
int quick_sort(vector<int>& data, int left, int right, int k)
{
int i = left;
int j = right;
int pivot = data[right];
int len = right - left + 1;
if (left < right)
{
// 从大到小对数组进行快排
while(i < j)
{
while(i < j && data[i] >= pivot) // 从左往右找第一个比 pivot 小的数
{
i++;
}
if (i < j)
{
data[j--] = data[i];
}
while(i < j && data[j] <= pivot) // 从右往左找第一个比 pivot 大的数
{
j--;
}
if (i < j)
{
data[i++] = data[j];
}
}
data[i] = pivot; // 此时 i == j
// pivot 此时位于索引 i 处，i - left + 1 表示 pivot 是第几大的数
int which_max = i - left + 1;
if (which_max == k) // pivot 正好是第 k 大的数
{
return pivot;
}
// 第 k 大的数在 pivot 右边，问题转化为找右边数组第 (k - which_max) 大的元素
// 比如 pivot 是第四大的数，要找第五大的数，则继续找右边数组第一大的数即可
else if(which_max < k)
{
return quick_sort(data, i + 1, right, k - which_max);
}
// 第 k 大的数在 pivot 左边，问题转化为找左边数组第 k 大的元素
// 比如 pivot 是第三大的数，要找第二大的数，则继续找左边数组第二大的数即可
else
{
return quick_sort(data, left, i - 1, k);
}
}
else
{
return pivot;
}
}
// 第二种快排思想
int quick_sort(vector<int>& data, int left, int right, int k)
{
int i = left;
int j = left;
int pivot = data[right];
int len = right - left + 1;
if (left < right)
{
// 从大到小对数组进行快排
for (; j < right; j++)
{
if (data[j] > pivot)
{
int temp = data[i];
data[i] = data[j];
data[j] = temp;
i++;
}
}
data[j] = data[i];
data[i] = pivot;
// pivot 此时位于索引 i 处，i - left + 1 表示 pivot 是第几大的数
int which_max = i - left + 1;
if (which_max == k) // pivot 正好是第 k 大的数
{
return pivot;
}
// 第 k 大的数在 pivot 右边，问题转化为找右边数组第 (k - which_max) 大的元素
// 比如 pivot 是第四大的数，要找第五大的数，则继续找右边数组第一大的数即可
else if(which_max < k)
{
return quick_sort(data, i + 1, right, k - which_max);
}
// 第 k 大的数在 pivot 左边，问题转化为找左边数组第 k 大的元素
// 比如 pivot 是第三大的数，要找第二大的数，则继续找左边数组第二大的数即可
else
{
return quick_sort(data, left, i - 1, k);
}
}
else
{
return pivot;
}
}
};
