2019-09-25 数组中的第K个最大元素

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

示例 1:

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

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

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

1、STL sort

C++

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
         sort(nums.begin(), nums.end(), greater<int>());
         return nums[k-1];
    }
};

2、快速排序

利用快速排序的思想，从数组 S 中随机找出一个元素 X，把数组分为两部分 Sa 和 Sb。Sa 中的元素大于等于 X，Sb 中元素小于 X。这时有两种情况：

Sa 中元素的个数小于 k，则 Sb 中的第 k-|Sa| 个元素即为第k大数；
Sa 中元素的个数大于等于 k，则返回 Sa 中的第 k 大数。时间复杂度近似为 O(n)

C++

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        if(k>n){
            return -1;
        }
        int index = quickSort(nums, 0, n-1, k);
        return nums[index];
    }
    
    int quickSort(vector<int>&nums, int l, int r, int k){
        if(l>=r){
            return l;
        }
        int p = partition(nums, l, r);
        if(p+1==k){
            return p;
        }
        if(p+1>k){
            return quickSort(nums, l, p-1, k);
        }else{
            return quickSort(nums, p+1, r, k);
        }
    }
    int partition(vector<int>&nums, int l, int r){
        int v= nums[l];
        int j = l;
        int i = l+1;
        while(i<=r){
            if(nums[i] >= v){
                int temp = nums[i];
                nums[i] = nums[j+1];
                nums[j+1] = temp;
                j++;
            }
            i++;
        }
        int t = nums[l];
        nums[l] = nums[j];
        nums[j] = t;
        return j;
    }
};