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

2021年3月12日 280点热度 0人点赞 0条评论

题目描述

在未排序的数组中找到第 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 ≤ 数组的长度

解题思路

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

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

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

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

代码示例

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

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论