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

题目描述

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

示例

示例 1:

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

示例 2:

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

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

解题思路

最自然的想法就是构造一个大根堆，然后删除 k-1 个堆顶元素然后就得到了第k大的元素，时间复杂度为 O(n log n) 。但是，今天我们使用快速排序的思想来解决第k大的问题。其目的在于熟悉对快速排序思想的掌握。

具体方法为：快速排序的每一次划分都会确定一个元素的位置，返回 index 。我们已知数组的长度 n ，因而可以确定这个元素是第几大的元素。然后就是快速排序的思想，以这个元素的位置为界，划分为左区和右区。如果正好就是找这个元素，直接返回；否则，运用这个元素的位置信息去判断在左区递归寻找还是右区递归寻找。时间复杂度也为 O(n log n) 。

这个方法在具体编程的时候有一个小坑，在判断一次划分某个元素是nums数组[left，right]中第几大元素的时候，方法为 right - index 。

这个方法还有优化的空间，可以使用随机化的快速排序算法，时间复杂度可以优化到 O ( n ) 。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int partion(std::vector<int>&nums,int left,int right)
{
     int temp=nums[left];
    while(left<right)
    {
        while(nums[right]>temp&&left<right) 
        {
            right--;
        }
        nums[left]=nums[right];
        while(nums[left]<=temp&&left<right) 
        {
            left++;
        }
        nums[right]=nums[left];
    }
    nums[left]=temp;
    return left;
}

int findKth(std::vector<int>&nums,int left,int right,int k)
{
    int ans;
    int index=partion(nums,left,right);
    int kth=right-index+1;
    if(kth==k) ans=nums[index];
    if(kth>k) ans=findKth(nums,index+1,right,k);
    if(kth<k) ans=findKth(nums,left,index-1,k-kth);
    return ans;
}

int findKthLargest(std::vector<int>&nums,int k)
{
    return findKth(nums,0,nums.size()-1,k);
}