欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++實現(xiàn)的O(n)復(fù)雜度內(nèi)查找第K大數(shù)算法示例

 更新時間:2017年08月15日 10:51:49   作者:葉赫那拉坤  
這篇文章主要介紹了C++實現(xiàn)的O(n)復(fù)雜度內(nèi)查找第K大數(shù)算法,結(jié)合實例形式分析了算法的原理以及具體實現(xiàn)方法,需要的朋友可以參考下

本文實例講述了C++實現(xiàn)的O(n)復(fù)雜度內(nèi)查找第K大數(shù)算法。分享給大家供大家參考,具體如下:

題目:是在一組數(shù)組(數(shù)組元素為整數(shù),可正可負可為0)中查找乘積最大的三個數(shù),最后輸出最大乘積。

從題目我們知道只有兩種結(jié)果存在:
1)三個最大的正整數(shù)相乘;
2)一個最大的正整數(shù)和兩個最小的負數(shù)相乘。

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

參考代碼:http://www.dbjr.com.cn/article/121189.htm

實現(xiàn)代碼:

#include <iostream>
#include <algorithm>
//分區(qū)
int partition(std::vector<int>&vec,int start,int end) {
 int value=vec[end];
 int tail=start-1;
 for(int i=start;i<end;++i){
  if(vec[i]<value){
   tail++;
   std::swap(vec[i],vec[tail]);
  }
 }
 tail++;
 std::swap(vec[tail],vec[end]);
 return tail;
}
long long solve(std::vector<int>&vec,int start,int end,int k) {
 //快排思想,進行分區(qū),快排復(fù)雜度為O(nlgn),但取最值只比較分區(qū)的一個區(qū)間,所以為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;//要比較的數(shù)的個數(shù)
 while(std::cin>>n) {
  std::vector<int> vec_i(n,0);//使用vector存儲n個數(shù)
  for(int i = 0; i < n; ++i) {
   std::cin>>vec_i[i];
  }
  int k;
  //最大的數(shù),index為n-1
  k = n - 1;
  long long x1 = solve(vec_i,0, n-1,k);
  //次大的數(shù),index為n-2
  k = n - 2;
  long long x2 = solve(vec_i,0, n-2,k);
  //第三大的數(shù)
  k = n - 3;
  long long x3 = solve(vec_i,0, n-3,k);
  long long Ans = x1 * x2 * x3;//最大的三個數(shù)的乘積
  if(n > 3) {
   //最小的數(shù),index為0
   k = 0;
   long long y1 = solve(vec_i,0, n-1,k);
   //次小的數(shù),index為1
   k = 1;
   long long y2 = solve(vec_i,0, n-2,k);
   Ans = std::max(Ans, y1*y2*x1);//兩者比較取最大
  }
  std::cout<<Ans;
 }
 return 0;
}

希望本文所述對大家C++程序設(shè)計有所幫助。

相關(guān)文章

  • 數(shù)據(jù)結(jié)構(gòu)之帶頭結(jié)點的單鏈表

    數(shù)據(jù)結(jié)構(gòu)之帶頭結(jié)點的單鏈表

    單鏈表是一種鏈式存取的數(shù)據(jù)結(jié)構(gòu),用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。鏈表中的數(shù)據(jù)是以結(jié)點來表示的,每個結(jié)點的構(gòu)成:數(shù)據(jù)域(數(shù)據(jù)元素的映象)?+?指針域(指示后繼元素存儲位置),元素就是存儲數(shù)據(jù)的存儲單元,指針就是連接每個結(jié)點的地址數(shù)據(jù)
    2023-07-07
  • 用C++實現(xiàn),將一句話里的單詞進行倒置的方法詳解

    用C++實現(xiàn),將一句話里的單詞進行倒置的方法詳解

    本篇文章是對用C++實現(xiàn),將一句話里的單詞進行倒置的方法進行了詳細的分析介紹,需要的朋友參考下
    2013-05-05
  • 淺析C/C++中動態(tài)鏈接庫的創(chuàng)建和調(diào)用

    淺析C/C++中動態(tài)鏈接庫的創(chuàng)建和調(diào)用

    下面小編就為大家?guī)硪黄獪\析C/C++中動態(tài)鏈接庫的創(chuàng)建和調(diào)用。小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考,一起跟隨小編過來看看吧
    2016-05-05
  • C語言棧與隊列面試題詳解

    C語言棧與隊列面試題詳解

    棧和隊列,嚴格意義上來說,也屬于線性表,因為它們也都用于存儲邏輯關(guān)系為 "一對一" 的數(shù)據(jù),但由于它們比較特殊,因此將其單獨作為一章,做重點講解
    2022-04-04
  • C++異常重拋出實例分析

    C++異常重拋出實例分析

    在本文里小編給大家分享的是關(guān)于C++異常重拋出實例分析,有興趣點朋友們可以跟著學(xué)習(xí)下。
    2020-05-05
  • C++常見獲取隨機數(shù)的方法小結(jié)

    C++常見獲取隨機數(shù)的方法小結(jié)

    這篇文章主要介紹了C++常見獲取隨機數(shù)的方法,結(jié)合實例形式總結(jié)分析了C++獲取隨機數(shù)的幾種常見方法與相關(guān)操作注意事項,需要的朋友可以參考下
    2018-05-05
  • C++中整形與浮點型如何在內(nèi)存中的存儲詳解

    C++中整形與浮點型如何在內(nèi)存中的存儲詳解

    大家好!這期和大家分享整形和浮點型是如何在數(shù)據(jù)是如何在內(nèi)存中存儲,下面文章具有一定的參考價值,需要的小伙伴可以參考一下
    2022-05-05
  • C++實現(xiàn)的泛型List類分享

    C++實現(xiàn)的泛型List類分享

    這篇文章主要介紹了C++實現(xiàn)的泛型List類分享,參考C#的List功能實現(xiàn),需要的朋友可以參考下
    2014-07-07
  • C++ 析構(gòu)函數(shù)與變量的生存周期實例詳解

    C++ 析構(gòu)函數(shù)與變量的生存周期實例詳解

    這篇文章主要介紹了C++ 析構(gòu)函數(shù)與變量的生存周期實例詳解的相關(guān)資料
    2017-06-06
  • 常用的C語言編程工具匯總

    常用的C語言編程工具匯總

    c語言編程軟件適于編寫系統(tǒng)軟件,是學(xué)習(xí)編程的同學(xué)們的必備軟件。c語言一種非常強大的計算機語言,應(yīng)用非常廣泛,不僅僅是在軟件開發(fā)上,而且各類科研都會用到c語言。今天小編給大家匯總下C語言的編程工具
    2018-01-01

最新評論