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;
                }
                else
                    i++;
            }
        }
        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;
}