周日

题目描述：

给定一个整数数组 nums，找到其中第 k 大的元素。注意，这里的第 k 大的元素指的是排序后第 k 大的元素，而不是第 k 个不同的元素。

示例：

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

设计思路：

该问题可以使用快速选择算法（QuickSelect Algorithm）来解决，快速选择是一种选择性能比概率选择更好的算法。

和快速排序思路类似，快速选择采用了分治法的思想，不过快速选择只需要对需要处理的数据进行一次划分，并接着选取其中的一部分继续处理。快速选择每次划分的时候都会把小于 pivot 的数放到 pivot 左边，大于等于 pivot 的数放在 pivot 右边，从而实现缩小问题规模的效果。

程序流程图：

开始
1. 进入快速选择函数
2. 选取 pivot 元素并将整个数组按照大小关系分为两部分
3. 如果 k 落在右半部分，继续对右半部分进行快速选择
   否则，继续对左半部分进行快速选择
4. 返回结果
结束

代码实现：

#include <iostream>
#include <vector>

using namespace std;

int partition(vector<int>& nums, int left, int right) {
    int pivot = nums[right], i = left;
    for (int j = left; j < right; ++j) {
        if (nums[j] > pivot) {
            swap(nums[i], nums[j]);
            ++i;
        }
    }
    swap(nums[i], nums[right]);
    return i;
}

int quickSelect(vector<int>& nums, int left, int right, int k) {
    int index = partition(nums, left, right);
    if (index - left == k - 1) {
        return nums[index];
    } else if (index - left > k - 1) {
        return quickSelect(nums, left, index - 1, k);
    } else {
        return quickSelect(nums, index + 1, right, k - index + left - 1);
    }
}

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

int main() {
    vector<int> nums = {3, 2, 1, 5, 6, 4};
    int k = 2;
    int result = findKthLargest(nums, k);
    cout << result << endl;
    return 0;
}