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

更新時(shí)間：2017年08月15日 10:51:49 作者：葉赫那拉坤

這篇文章主要介紹了C++實(shí)現(xiàn)的O(n)復(fù)雜度內(nèi)查找第K大數(shù)算法,結(jié)合實(shí)例形式分析了算法的原理以及具體實(shí)現(xiàn)方法,需要的朋友可以參考下

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

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

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

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

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

實(shí)現(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) {
 //快排思想，進(jìn)行分區(qū)，快排復(fù)雜度為O(nlgn),但取最值只比較分區(qū)的一個(gè)區(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ù)的個(gè)數(shù)
 while(std::cin>>n) {
  std::vector<int> vec_i(n,0);//使用vector存儲(chǔ)n個(gè)數(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;//最大的三個(gè)數(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;
}

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

您可能感興趣的文章:

相關(guān)文章

數(shù)據(jù)結(jié)構(gòu)之帶頭結(jié)點(diǎn)的單鏈表
單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu)，用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。鏈表中的數(shù)據(jù)是以結(jié)點(diǎn)來(lái)表示的，每個(gè)結(jié)點(diǎn)的構(gòu)成：數(shù)據(jù)域(數(shù)據(jù)元素的映象)?+?指針域(指示后繼元素存儲(chǔ)位置)，元素就是存儲(chǔ)數(shù)據(jù)的存儲(chǔ)單元，指針就是連接每個(gè)結(jié)點(diǎn)的地址數(shù)據(jù)
2023-07-07
用C++實(shí)現(xiàn),將一句話里的單詞進(jìn)行倒置的方法詳解
本篇文章是對(duì)用C++實(shí)現(xiàn),將一句話里的單詞進(jìn)行倒置的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下
2013-05-05
淺析C/C++中動(dòng)態(tài)鏈接庫(kù)的創(chuàng)建和調(diào)用
下面小編就為大家?guī)?lái)一篇淺析C/C++中動(dòng)態(tài)鏈接庫(kù)的創(chuàng)建和調(diào)用。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考，一起跟隨小編過(guò)來(lái)看看吧
2016-05-05
C語(yǔ)言棧與隊(duì)列面試題詳解
棧和隊(duì)列，嚴(yán)格意義上來(lái)說(shuō)，也屬于線性表，因?yàn)樗鼈円捕加糜诖鎯?chǔ)邏輯關(guān)系為 "一對(duì)一" 的數(shù)據(jù)，但由于它們比較特殊，因此將其單獨(dú)作為一章，做重點(diǎn)講解
2022-04-04
C++異常重拋出實(shí)例分析
在本文里小編給大家分享的是關(guān)于C++異常重拋出實(shí)例分析，有興趣點(diǎn)朋友們可以跟著學(xué)習(xí)下。
2020-05-05
C++常見(jiàn)獲取隨機(jī)數(shù)的方法小結(jié)
這篇文章主要介紹了C++常見(jiàn)獲取隨機(jī)數(shù)的方法,結(jié)合實(shí)例形式總結(jié)分析了C++獲取隨機(jī)數(shù)的幾種常見(jiàn)方法與相關(guān)操作注意事項(xiàng),需要的朋友可以參考下
2018-05-05
C++中整形與浮點(diǎn)型如何在內(nèi)存中的存儲(chǔ)詳解
大家好！這期和大家分享整形和浮點(diǎn)型是如何在數(shù)據(jù)是如何在內(nèi)存中存儲(chǔ)，下面文章具有一定的參考價(jià)值,需要的小伙伴可以參考一下
2022-05-05
C++實(shí)現(xiàn)的泛型List類分享
這篇文章主要介紹了C++實(shí)現(xiàn)的泛型List類分享,參考C#的List功能實(shí)現(xiàn),需要的朋友可以參考下
2014-07-07
C++ 析構(gòu)函數(shù)與變量的生存周期實(shí)例詳解
這篇文章主要介紹了C++ 析構(gòu)函數(shù)與變量的生存周期實(shí)例詳解的相關(guān)資料
2017-06-06
常用的C語(yǔ)言編程工具匯總
c語(yǔ)言編程軟件適于編寫系統(tǒng)軟件，是學(xué)習(xí)編程的同學(xué)們的必備軟件。c語(yǔ)言一種非常強(qiáng)大的計(jì)算機(jī)語(yǔ)言，應(yīng)用非常廣泛，不僅僅是在軟件開(kāi)發(fā)上，而且各類科研都會(huì)用到c語(yǔ)言。今天小編給大家匯總下C語(yǔ)言的編程工具
2018-01-01