C++實現(xiàn)的O(n)復(fù)雜度內(nèi)查找第K大數(shù)算法示例
本文實例講述了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),用一組地址任意的存儲單元存放線性表中的數(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),將一句話里的單詞進行倒置的方法進行了詳細的分析介紹,需要的朋友參考下2013-05-05淺析C/C++中動態(tài)鏈接庫的創(chuàng)建和調(diào)用
下面小編就為大家?guī)硪黄獪\析C/C++中動態(tài)鏈接庫的創(chuàng)建和調(diào)用。小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考,一起跟隨小編過來看看吧2016-05-05C++ 析構(gòu)函數(shù)與變量的生存周期實例詳解
這篇文章主要介紹了C++ 析構(gòu)函數(shù)與變量的生存周期實例詳解的相關(guān)資料2017-06-06