牛客題霸 [尋找第K大] C++題解/答案

題目描述

有一個(gè)整數(shù)數(shù)組，請(qǐng)你根據(jù)快速排序的思路，找出數(shù)組中第K大的數(shù)。

給定一個(gè)整數(shù)數(shù)組a,同時(shí)給定它的大小n和要找的K(K在1到n之間)，請(qǐng)返回第K大的數(shù)，保證答案存在。

題目：

利用快排+二分

題解：

class Finder { public:int findKth(vector<int> a, int n, int K) {// write code here、return find(a,0,n-1,n-K+1);}int find(vector<int>&a,int l,int r,int K){if(l==r) return a[l];int i=l-1;int j=r+1;int x=a[l+r>>1];while(i<j){do i++;while(a[i]<x);do j--;while(x<a[j]);if(i<j) swap(a[i],a[j]);}int s=j-l+1;if(K<=s) return find(a,l,j,K);else return find(a,j+1,r,K-s);} };

總結(jié)

以上是生活随笔為你收集整理的牛客题霸 [寻找第K大] C++题解/答案的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。