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

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

思路：最开始排序算法，弄完之后直接按照要求选择，可惜题目对时间复杂度有要求，只能上快排，但是快排并不是直接满足，还需要在基础上优化。快排采取分治的思想，正常递归需要子串都进行排序，最后合并，但是找出结果有个便利的点就是可以判断在那个串里面，选择性的进行快排来加速。

#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;
}