程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 編程之美2.5——尋找最大的K個數

編程之美2.5——尋找最大的K個數

編輯:C++入門知識

問題:
從一組數中選出其中最大的K個數,當這組數的個數為幾百、幾百萬、幾百億時分別適合采用哪些算法?
 
個數為幾百時,使用順序統計法(看算法導論第9章):
     算法思想是對輸入數組進行遞歸劃分,一邊的數據小於選定數,另一邊的數據大於等於選定數。但和快速排序不同的是,快速排序會遞歸處理劃分的兩邊,而順序統計法只處理劃分的一邊。其隨機化算法的期望時間為O(n)。
[cpp]
#include <iostream> 
#include <cstdlib> 
using namespace std; 
 
#define MAXN 103 
int A[MAXN]; 
 
void select(int u, int v, int k) 

    int s = rand()%(v-u+1)+u; 
    int a = A[s]; 
    A[s] = A[u]; 
    A[u] = a; 
    int i, j=u; 
    for (i=u; i<=v; i++) 
        if (A[i] > a) 
        { 
            int tmp = A[++j]; 
            A[j] = A[i]; 
            A[i] = tmp; 
        } 
    A[u] = A[j]; 
    A[j] = a; 
    if (j == k) return; 
    else if (j < k) 
        select(j+1, v, k); 
    else 
        select(u, j-1, k); 

 
int main() 

    int n, k, i, j; 
    cin >> n >> k; 
    for (i=0; i<n; i++) 
        cin >> A[i]; 
    select(0, n-1, k-1); 
    for (i=0; i<k; i++) 
        cout << A[i] << " "; 
    cout << endl; 

個數為幾百萬時,數據量較大不適合全裝入內存中,能容忍多次訪問,可使用二分中值法(用法有點奇怪,個人不太喜歡):
      本質上是通過二分思想找出第K大的數的值。算法從[Min, Max]開始逐漸縮小第K大的數取值的范圍,時間復雜度為O(N*log(Max-Min))。
[cpp] 
#include <iostream> 
#include <cstdlib> 
using namespace std; 
 
 
int binary(FILE *in, int v) 

    rewind(in); 
    int a, sum = 0; 
    while (fscanf(in, "%d", &a)!=EOF) 
    { 
        if (a >= v) sum++; 
    } 
    return sum; 

 
void finded(FILE *in, int v) 

    rewind(in); 
    int a; 
    while (fscanf(in, "%d", &a)!=EOF) 
    { 
        if (a >= v)  
            cout << a << " "; 
    } 
    cout << endl; 

 
int main() 

    int n, k; 
    cin >> n >> k; 
    FILE* in = fopen("dat.txt","r"); 
    int min, max; 
    int a; 
    fscanf(in, "%d", &a); 
    min = max = a; 
    while (fscanf(in, "%d", &a)!=EOF) 
    { 
        if (a < min) min = a; 
        if (a > max) max = a; 
    } 
    while (max > min) 
    { 
        int mid = (min+max)/2; 
        int ns = binary(in, mid); 
        if (ns == k) 
        { 
            finded(in, (min+max)/2); 
            break; 
        } 
        else if (ns < k) max = mid; 
        else min = mid; 
    } 

 
個數為幾萬億時,數據量較大不適合全裝入內存中,且無法容忍多次訪問,所有數據只能訪問一次,推薦使用最小堆法(上面那種情況也推薦使用這個方法),但要求K較小,否則無法在內存存下整個最小堆。
      用容量為K的最小堆來存儲最大的K個數,最小堆的堆頂元素就是最大K個數中最小的一個。每次考慮一個新的元素時,將其與堆頂的元素進行比較,只有當它大於堆頂元素時,才用其替換堆頂元素,並更新最小堆。時間復雜度為O(N*logK)。
[cpp] www.2cto.com
#include <iostream> 
 
using namespace std; 
 
#define MAXN 103 
 
int H[MAXN]; 
 
void upshift(int s) 

    int tmp = H[s]; 
    while (s>1 && H[s>>1] > tmp) 
    { 
        H[s] = H[s>>1]; 
        s >>= 1; 
    } 
    H[s] = tmp; 

 
void downshift(int n) 

    int tmp = H[1]; 
    int i=1, j=i<<1; 
    while (j <= n) 
    { 
        if (j+1 <= n && H[j+1] < H[j]) j++; 
        if (H[j] < tmp) H[i] = H[j]; 
        else break; 
        i = j; 
        j = j<<1; 
    } 
    H[i] = tmp; 

 
int main() 

    int n, k, i, A; 
    cin >> n >> k; 
    for (i=1; i<=k; i++) 
    { 
        cin >> H[i]; 
        upshift(i); 
    } 
    for (; i<=n; i++) 
    { 
        cin >> A; 
        if (A > H[1]) 
        { 
            H[1] = A; 
            downshift(k); 
        } 
    } 
    for (i=1; i<=k; i++) 
        cout << H[i] << " "; 
    cout << endl; 

作者:linyunzju

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved