給定整數(shù)數(shù)組 nums 和整數(shù) k，請返回數(shù)組中第 k 個最大的元素。

請注意，你需要找的是數(shù)組排序后的第 k 個最大的元素，而不是第 k 個不同的元素。

你必須設(shè)計并實現(xiàn)時間復(fù)雜度為 O(n) 的算法解決此問題。

思路：最開始排序算法，弄完之后直接按照要求選擇，可惜題目對時間復(fù)雜度有要求，只能上快排，但是快排并不是直接滿足，還需要在基礎(chǔ)上優(yōu)化?？炫挪扇》种蔚乃枷?#xff0c;正常遞歸需要子串都進行排序，最后合并，但是找出結(jié)果有個便利的點就是可以判斷在那個串里面，選擇性的進行快排來加速。

#include <iostream>
#include <vector>using namespace std;
//選擇排序
// class Solution {
// public:
//     int findKthLargest(vector<int>& nums, int k) {
//         for (int i = 0; i < nums.size(); i++){
//             int min_index = i; // 記錄最小值的索引
//             for (int j = i; j < nums.size(); j++){
//                 if (nums[j] < nums[min_index]){
//                     min_index = j;
//                 }
//             }
//             swap(nums[min_index], nums[i]);
//         }
//         return nums[nums.size() - k];
//     }
// };class Solution {
public:int aparthSort(vector<int>& nums, int left, int right){int i = left, j = right;int pivot = nums[left];while (i < j) {while (i < j) {if (nums[j] < pivot) {nums[i] = nums[j];i++;break;}else j--;}while (i < j) {if (nums[i] > pivot) {nums[j] = nums[i];j--;break;}elsei++;}}nums[i] = pivot;return i;}int sort (vector<int>& nums, int left, int right, int k) {int mid;if (left < right){mid = aparthSort(nums, left, right);if (mid == nums.size() - k) return nums[mid];else if (mid > nums.size() - k) return sort(nums, left, mid - 1, k);else return sort(nums, mid + 1, right, k);}else    return nums[nums.size() - k];}int findKthLargest(vector<int>& nums, int k) {int res =  sort(nums, 0, nums.size() - 1, k);return res;}
};int main(){Solution s;vector<int> nums = {3,2,1,5,6,4};// vector<int> nums = {1};int k = 4;cout << s.findKthLargest(nums, k) << endl;for (int i = 0; i < nums.size(); i++){cout << nums[i] << " ";}return 0;
}