小代碼尋找K個(gè)最大的數(shù)

 /*****************************
 復(fù)雜度：

 
 ***************************/
 
#include<iostream>
#include<assert.h>
#include<vector>  
#include<stdlib.h> 
#include<time.h>
using namespace std;
 
#define N 1000 
#define K 100
void AdjustDown(int *a, size_t root, size_t size) 
{ //向下調(diào)整小堆
    size_t parent = root;
    size_t child = parent * 2 + 1;
    while (child < size)
    {
        if (child + 1 < size && a[child] > a[child + 1])
        {
            ++child;
        }
        if (a[parent] > a[child])
        {
            swap(a[parent], a[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else//注意不滿足交換條件時(shí)跳出本次循環(huán)
        {
            break;
        }
    }
}
void GetTopk(const vector<int>& Vnumber, int n, int k)//N個(gè)數(shù)中找最大的前k個(gè)數(shù)--小堆實(shí)現(xiàn)
{
    assert(n>k);
    int *TopkArray = new int[k];//通過前k個(gè)元素建立含有k個(gè)元素的堆
    for (size_t i = 0; i < k; i++)
    {
        TopkArray[i] = Vnumber[i];
    }
    for (int i = (k - 2) / 2; i >= 0; --i)//建小堆
    {
        AdjustDown(TopkArray, i, k);
    }
    //從第k個(gè)元素開始到第n個(gè)元素分別與堆頂元素進(jìn)行比較，較大數(shù)據(jù)入堆頂，再對整個(gè)堆進(jìn)行下調(diào)，使堆頂存放最小元素（小堆）
    for (size_t i = k; i < n; ++i)
    {
        if (Vnumber[i]  > TopkArray[0])
        {
            TopkArray[0] = Vnumber[i];
            AdjustDown(TopkArray, 0, k);
        }
    }
    size_t count = 0;
    for (size_t i = 0; i < k; ++i)//打印k個(gè)最大數(shù)據(jù)，即堆中所有元素
    {
        cout << TopkArray[i] << " ";
        ++count;
        if (count % 10 == 0)
        {
            cout << endl;
        }
    }
    cout << endl;
    delete[] TopkArray;//注意釋放TopkArray所占的內(nèi)存
    TopkArray = NULL;
}

void CreateVnumber(vector<int>& Vnumber)//創(chuàng)建N個(gè)數(shù)
{
    srand((unsigned int)time(NULL));
    //srand(time(0));
    Vnumber.reserve(N);
    for (size_t i = 0; i<N; i++)
    {
        Vnumber.push_back(rand() % 1000);//產(chǎn)生N個(gè)隨機(jī)值
    }
    for (size_t i = K; i < N; ++i)
    {
        Vnumber[i] *= 100;
    }
}
int main()
{
    vector<int> Vnumber;
    CreateVnumber(Vnumber);
    GetTopk(Vnumber, N, K);
    //int length = Vnumber.size();
    //for(int i=0;i<length;i++)
    //{
    //   cout<<Vnumber[i]<<" ";
   // }
 	return 0;
}

標(biāo)題名稱：小代碼尋找K個(gè)最大的數(shù)
轉(zhuǎn)載來于：http://muchs.cn/article0/jiosio.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供面包屑導(dǎo)航、微信公眾號(hào)、企業(yè)建站、移動(dòng)網(wǎng)站建設(shè)、品牌網(wǎng)站建設(shè)、App開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)