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

目录

一、问题描述

二、解题思路

整体思路

具体思路

三、代码实现

一、问题描述

二、解题思路

整体思路

可以采用区间划分的快速选择排序算法来解决这个问题。本题的思路与leetcode 912 排序数组-CSDN博客的思路一致。

具体思路

(1)采用三指针区间划分的方法将区间划分成三个部分：

<1>区间[l,left]，区间内的所有数字均小于key；

<2>区间[left+1,right-1]，区间内的所有数字均为key，区间中元素的个数b=right-left-1；

<3>区间[right,r]，区间内所有数字均大于key，区间中元素的个数a=r-right+1;

区间划分为三部分可参考：leetcode 75 颜色分类-CSDN博客

(2)因为要返回第K大的数字，所以有以下三种情况：

<1>如果a>=k，说明第K大的数落在[right,r]这个区间里面，返回qsort(nums,right,r,k)即可；

<2>如果a+b>=k，说明第K大的数落在[left+1,right-1]这个区间里面，区间的所有元素均为key，直接返回K即可；

<3>如果第K大的数落在[l,left]这个区间里面，返回qsort(nums,l,left,k-a-b)即可；

三、代码实现

时间复杂度：T(n)=O(n)

空间复杂度：S(n)=O(1)

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        //产生随机数种子
        srand(time(NULL));
        return qsort(nums,0,nums.size()-1,k);
    }

    //区间划分实现快速选择排序
    int qsort(vector<int>& nums,int l,int r,int k){
        //递归出口
        if(l==r) return nums[l];

        //随机选择基准元素
        int key=GetRandom(nums,l,r);
        //根据基准元素分三块
        int left=l-1,right=r+1,i=l;
        while(i<right){
            if(nums[i]==key) i++;
            else if(nums[i]<key) swap(nums[++left],nums[i++]);
            else swap(nums[--right],nums[i]);
        }

        //[l,left],[left+1,right-1],[right,r]三个区间
        int c=r-right+1,b=right-left-1;
        //分情况讨论
        if(c>=k) return qsort(nums,right,r,k);
        else if(b+c>=k) return key;
        else return qsort(nums,l,left,k-b-c);

    }

    //产生随机数
    int GetRandom(vector<int>& nums,int left,int right){
        int r=rand();
        return nums[left+r%(right-left+1)];
    }
};