C++實(shí)現(xiàn)的O(n)復(fù)雜度內(nèi)查找第K大數(shù)算法示例
本文實(shí)例講述了C++實(shí)現(xiàn)的O(n)復(fù)雜度內(nèi)查找第K大數(shù)算法。分享給大家供大家參考,具體如下:
題目:是在一組數(shù)組(數(shù)組元素為整數(shù),可正可負(fù)可為0)中查找乘積最大的三個數(shù),最后輸出最大乘積。
從題目我們知道只有兩種結(jié)果存在:
1)三個最大的正整數(shù)相乘;
2)一個最大的正整數(shù)和兩個最小的負(fù)數(shù)相乘。
所以我們需要找出數(shù)組中最大的三個數(shù)的乘積m,然后與數(shù)組中最小的兩個數(shù)相乘再與最大的數(shù)相乘的結(jié)果n,然后比較m,n,選出最大的數(shù)即為最終的結(jié)果。
參考代碼://www.jb51.net/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ū)的一個區(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è)計(jì)有所幫助。
上一篇:QT開發(fā)應(yīng)用程序的歡迎界面實(shí)例
欄 目:C語言
本文標(biāo)題:C++實(shí)現(xiàn)的O(n)復(fù)雜度內(nèi)查找第K大數(shù)算法示例
本文地址:http://mengdiqiu.com.cn/a1/Cyuyan/1250.html
您可能感興趣的文章
- 04-02c語言的正則匹配函數(shù) c語言正則表達(dá)式函數(shù)庫
- 04-02c語言中對數(shù)函數(shù)的表達(dá)式 c語言中對數(shù)怎么表達(dá)
- 04-02c語言沒有round函數(shù) round c語言
- 04-02C語言中怎么打出三角函數(shù) c語言中怎么打出三角函數(shù)的值
- 01-10c語言求1+2+...+n的解決方法
- 01-10求子數(shù)組最大和的解決方法詳解
- 01-10深入理解約瑟夫環(huán)的數(shù)學(xué)優(yōu)化方法
- 01-10深入二叉樹兩個結(jié)點(diǎn)的最低共同父結(jié)點(diǎn)的詳解
- 01-10數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)- 解析最少換車次數(shù)的問題詳解
- 01-10c語言 跳臺階問題的解決方法


閱讀排行
本欄相關(guān)
- 04-02c語言函數(shù)調(diào)用后清空內(nèi)存 c語言調(diào)用
- 04-02func函數(shù)+在C語言 func函數(shù)在c語言中
- 04-02c語言的正則匹配函數(shù) c語言正則表達(dá)
- 04-02c語言用函數(shù)寫分段 用c語言表示分段
- 04-02c語言中對數(shù)函數(shù)的表達(dá)式 c語言中對
- 04-02c語言編寫函數(shù)冒泡排序 c語言冒泡排
- 04-02c語言沒有round函數(shù) round c語言
- 04-02c語言分段函數(shù)怎么求 用c語言求分段
- 04-02C語言中怎么打出三角函數(shù) c語言中怎
- 04-02c語言調(diào)用函數(shù)求fibo C語言調(diào)用函數(shù)求
隨機(jī)閱讀
- 08-05織夢dedecms什么時候用欄目交叉功能?
- 01-10SublimeText編譯C開發(fā)環(huán)境設(shè)置
- 01-10使用C語言求解撲克牌的順子及n個骰子
- 01-10C#中split用法實(shí)例總結(jié)
- 01-11Mac OSX 打開原生自帶讀寫NTFS功能(圖文
- 04-02jquery與jsp,用jquery
- 08-05dedecms(織夢)副欄目數(shù)量限制代碼修改
- 01-10delphi制作wav文件的方法
- 01-11ajax實(shí)現(xiàn)頁面的局部加載
- 08-05DEDE織夢data目錄下的sessions文件夾有什