這篇文章主要介紹了C++如何實現的O(n)復雜度內查找第K大數，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

專注于為中小企業提供成都做網站、網站設計服務,電腦端+手機端+微信端的三站合一,更高效的管理,為中小企業聶拉木免費做網站提供優質的服務。我們立足成都，凝聚了一批互聯網行業人才，有力地推動了上1000家企業的穩健成長，幫助中小企業通過網站建設實現規模擴充和轉變。

具體如下：

題目：是在一組數組（數組元素為整數，可正可負可為0）中查找乘積大的三個數，最后輸出大乘積。

從題目我們知道只有兩種結果存在：
1）三個大的正整數相乘；
2）一個大的正整數和兩個最小的負數相乘。

所以我們需要找出數組中大的三個數的乘積m，然后與數組中最小的兩個數相乘再與大的數相乘的結果n，然后比較m,n，選出大的數即為最終的結果。

參考代碼：https://www.jb51.net/article/121189.htm

實現代碼：

#include 
#include 
//分區
int partition(std::vector&vec,int start,int end) {
 int value=vec[end];
 int tail=start-1;
 for(int i=start;i&vec,int start,int end,int k) {
 //快排思想，進行分區，快排復雜度為O(nlgn),但取最值只比較分區的一個區間，所以為O(n)
 int now = partition(vec,start,end);
 if(k < now)
  return solve(vec,start,now-1,k);
 else if(k > now)
  return solve(vec,now+1,end,k);
 else
  return vec[now];
}
int main() {
 int n;//要比較的數的個數
 while(std::cin>>n) {
  std::vector vec_i(n,0);//使用vector存儲n個數
  for(int i = 0; i < n; ++i) {
   std::cin>>vec_i[i];
  }
  int k;
  //大的數，index為n-1
  k = n - 1;
  long long x1 = solve(vec_i,0, n-1,k);
  //次大的數，index為n-2
  k = n - 2;
  long long x2 = solve(vec_i,0, n-2,k);
  //第三大的數
  k = n - 3;
  long long x3 = solve(vec_i,0, n-3,k);
  long long Ans = x1 * x2 * x3;//大的三個數的乘積
  if(n > 3) {
   //最小的數，index為0
   k = 0;
   long long y1 = solve(vec_i,0, n-1,k);
   //次小的數，index為1
   k = 1;
   long long y2 = solve(vec_i,0, n-2,k);
   Ans = std::max(Ans, y1*y2*x1);//兩者比較取大
  }
  std::cout<
感謝你能夠認真閱讀完這篇文章，希望小編分享的“C++如何實現的O(n)復雜度內查找第K大數”這篇文章對大家有幫助，同時也希望大家多多支持創新互聯建站，關注創新互聯網站建設公司行業資訊頻道，更多相關知識等著你來學習!
另外有需要云服務器可以了解下創新互聯建站www.cdcxhl.com，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業上云的綜合解決方案，具有“安全穩定、簡單易用、服務可用性高、性價比高”等特點與優勢，專為企業上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。
            

            新聞標題：C++如何實現的O(n)復雜度內查找第K大數-創新互聯            

            分享路徑：http://m.jcarcd.cn/article/dijipd.html