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

題目描述

創(chuàng)新互聯(lián)服務(wù)項(xiàng)目包括二道網(wǎng)站建設(shè)、二道網(wǎng)站制作、二道網(wǎng)頁(yè)制作以及二道網(wǎng)絡(luò)營(yíng)銷(xiāo)策劃等。多年來(lái)，我們專(zhuān)注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，二道網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶(hù)以成都為中心已經(jīng)輻射到二道省份的部分城市，未來(lái)相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶(hù)的支持與信任！

：在好幾億個(gè)數(shù)據(jù)中找出最大或最小的K個(gè)數(shù)。


分析：這幾億的數(shù)據(jù)肯定不能一起加載到內(nèi)存中去，更不能對(duì)這些數(shù)據(jù)直接進(jìn)行排序，因此我們這里講用數(shù)據(jù)結(jié)構(gòu)中的 堆 來(lái)解決這個(gè)問(wèn)題。

假定這里要從100000個(gè)數(shù)據(jù)中找出最大的100個(gè)數(shù)據(jù)，這樣是為了描述方便，我們這里直接用一個(gè)數(shù)組來(lái)存儲(chǔ)這個(gè)100000個(gè)數(shù)據(jù)，如果數(shù)據(jù)多達(dá)好幾億，則只需將這些數(shù)據(jù)放入文件中進(jìn)行讀寫(xiě)即可，這里為了描述問(wèn)題方便就這樣假定。


步驟：

  1. 取出這些數(shù)據(jù)中前100個(gè)數(shù)據(jù)，然后用這些數(shù)據(jù)建立一個(gè)小堆；

  2. 從第101個(gè)數(shù)據(jù)開(kāi)始，每讀取一個(gè)數(shù)據(jù)，就與堆頂?shù)脑剡M(jìn)行比較，如果該數(shù)據(jù)大于堆頂?shù)臄?shù)據(jù)，則將堆頂?shù)臄?shù)據(jù)替換為該數(shù)據(jù)，并對(duì)這個(gè)小堆進(jìn)行調(diào)整。

  3. 重復(fù)步驟2，等到所有數(shù)據(jù)都取完后，則留下的這個(gè)堆中的100個(gè)元素，就是我們要得到的最大的100個(gè)數(shù)。

代碼如下：

#pragma once
#include<iostream>
#include<time.h>
using namespace std;

#define N 100000  //N個(gè)數(shù)據(jù)
#define K 100     //最大或最小數(shù)據(jù)的個(gè)數(shù)


//仿函數(shù)，可以選最大的K個(gè)數(shù)，也可以選最小的K個(gè)數(shù)
template<class T>
struct Less
{
	bool operator()(const T& num1, const T& num2)
	{
		return num1 < num2;
	}
};

template<class T>
struct Greater
{
	bool operator()(const T& num1, const T& num2)
	{
		return num1 > num2;
	}
};


template<class T, class com = Less>  //默認(rèn)建小堆
class Heap
{
public:

	Heap(const T* a, size_t size)
		:MaxOrMinK(new T[size])
		, _size(size)
	{
		for (size_t i = 0; i < _size; ++i)
		{
			MaxOrMinK[i] = a[i];
		}
	}

	~Heap()
	{
		if (_size > 0)
			delete[] MaxOrMinK;
	}

	void CreatHeap()  // 建堆,(小/大)
	{
		for (int i = (_size - 2) / 2; i >= 0; --i)
		{
			AdjustDown(MaxOrMinK, _size, i);
		}
	}

	void GetK(const T* array, size_t size)  //從array中選出最大(或最小)的K個(gè)數(shù)
	{
		for (int i = K; i < size; ++i)
		{
			if (com()(MaxOrMinK[0], array[i]))
			{
				MaxOrMinK[0] = array[i];
				AdjustDown(MaxOrMinK, _size, 0);
			}
		}
	}

	void Print()
	{
		if (_size > 0)
		{
			for (size_t i = 0; i < _size; ++i)
			{
				cout << MaxOrMinK[i] << endl;
			}
		}
	}

protected:
	void AdjustDown(T*& a, size_t size, size_t root)
	{
		size_t child = root * 2 + 1;  //計(jì)算左孩子

		while (child < size)
		{
			if (child + 1 < size && com()(a[child + 1], a[child]))
			{
				++child;
			}
			if (com()(a[child], a[root]))
			{
				std::swap(a[root], a[child]);
				root = child;
				child = root * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}


private:
	T* MaxOrMinK;
	size_t _size;
};


void Test1()
{
	int randNum[N];
	srand(time(NULL));
	for (int i = 0; i < N; ++i)
	{
		int tmp = rand() % 10000;
		randNum[i] = tmp;  //產(chǎn)生N個(gè)10000以?xún)?nèi)的隨機(jī)數(shù)
	}

	Heap<int, Less<int>> get_K(randNum, K);  //小堆 選最大的K個(gè)數(shù)
	get_K.CreatHeap();
	get_K.GetK(randNum, N);
	get_K.Print();
}

void Test2()
{
	int randNum[N];
	srand(time(NULL));
	for (int i = 0; i < N; ++i)
	{
		int tmp = rand() % 10000;
		randNum[i] = tmp;  //產(chǎn)生N個(gè)10000以?xún)?nèi)的隨機(jī)數(shù)
	}

	Heap<int, Greater<int>> get_K(randNum, K);  //大堆 選最小的K個(gè)數(shù)
	get_K.CreatHeap();
	get_K.GetK(randNum, N);
	get_K.Print();
}

網(wǎng)站欄目：尋找最大或最小的K個(gè)數(shù)
網(wǎng)頁(yè)路徑：http://muchs.cn/article32/ghgjsc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站建設(shè)、品牌網(wǎng)站制作、手機(jī)網(wǎng)站建設(shè)、自適應(yīng)網(wǎng)站、商城網(wǎng)站、建站公司

廣告

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

成都網(wǎng)站建設(shè)