215.数组中的第K个最大元素-C++

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

###问题描述给定一个整数数组 `nums` 和一个整数 `k`，请找出该数组中第 `k` 大的元素。

### 示例* 输入：`nums = [3,2,1,5,6,4], k =2`
输出：`5`

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

### 解决方案#### 方法一：使用堆栈（时间复杂度为 O(n log n)）

我们可以使用一个最大堆来存储数组中的元素。每次插入新元素时，我们都需要将其与堆顶的元素进行比较。如果新元素大于堆顶的元素，则交换它们并继续向下调整堆。

cppclass Solution {
public:
 int findKthLargest(vector<int>& nums, int k) {
 // 使用最大堆来存储数组中的元素 priority_queue<int> maxHeap;
 for (int num : nums) {
 // 将新元素插入堆中，并向下调整堆 maxHeap.push(num);
 if (maxHeap.size() > k) {
 // 如果堆的大小超过 k，弹出堆顶的元素 maxHeap.pop();
 }
 }
 // 堆中剩余的元素就是第 k 大的元素 return maxHeap.top();
 }
};

#### 方法二：使用快速选择算法（时间复杂度为 O(n)）

我们可以使用快速选择算法来找到数组中的第 k 大元素。该算法首先随机选择一个 pivot 元素，然后将剩余的元素分成两部分：小于 pivot 的元素和大于 pivot 的元素。

cppclass Solution {
public:
 int findKthLargest(vector<int>& nums, int k) {
 // 使用快速选择算法来找到第 k 大的元素 return quickSelect(nums,0, nums.size() -1, k);
 }
private:
 int quickSelect(vector<int>& nums, int left, int right, int k) {
 if (left == right) {
 // 如果剩余的元素只有一个，则返回该元素 return nums[left];
 }
 // 随机选择 pivot 元素 int pivotIndex = partition(nums, left, right);
 // 将剩余的元素分成两部分：小于 pivot 的元素和大于 pivot 的元素 if (k == pivotIndex +1) {
 // 如果 k 等于 pivot 的索引，则返回 pivot 元素 return nums[pivotIndex];
 } else if (k < pivotIndex +1) {
 // 如果 k 小于 pivot 的索引，则递归调用 quickSelect 来找到第 k 大的元素 return quickSelect(nums, left, pivotIndex -1, k);
 } else {
 // 如果 k 大于 pivot 的索引，则递归调用 quickSelect 来找到第 k 大的元素 return quickSelect(nums, pivotIndex +1, right, k);
 }
 }
 int partition(vector<int>& nums, int left, int right) {
 // 随机选择 pivot 元素 int pivot = nums[left];
 // 将剩余的元素分成两部分：小于 pivot 的元素和大于 pivot 的元素 int i = left +1;
 int j = right;
 while (true) {
 while (i <= j && nums[i] < pivot) {
 i++;
 }
 while (i <= j && nums[j] > pivot) {
 j--;
 }
 if (i >= j) {
 break;
 }
 // 交换 i 和 j 的元素 swap(nums[i], nums[j]);
 }
 // 将 pivot 元素移动到正确的位置 swap(nums[left], nums[j]);
 return j;
 }
};

### 总结在本题中，我们需要找到数组中的第 k 大元素。我们可以使用堆栈或快速选择算法来解决这个问题。堆栈方法的时间复杂度为 O(n log n)，而快速选择算法的时间复杂度为 O(n)。快速选择算法是更有效的方法，特别是在大型数组中。

###代码注释* `findKthLargest` 函数：该函数用于找到数组中的第 k 大元素。
* `quickSelect` 函数：该函数用于使用快速选择算法来找到第 k 大的元素。
* `partition` 函数：该函数用于将剩余的元素分成两部分：小于 pivot 的元素和大于 pivot 的元素。

### 示例代码

cppint main() {
 vector<int> nums = {3,2,1,5,6,4};
 int k =2;
 Solution solution;
 int result = solution.findKthLargest(nums, k);
 cout << "第 " << k << " 大的元素是：" << result << endl;
 return0;
}

### 最终答案第 k 大的元素是5。