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