寻找最大或最小的K个数

发布时间:2020-07-21 00:00:51 作者:duanjiatao
来源:网络 阅读:408


题目描述


在好几亿个数据中找出最大或最小的K个数。


分析:这几亿的数据肯定不能一起加载到内存中去,更不能对这些数据直接进行排序,因此我们这里讲用数据结构中的 堆 来解决这个问题。


假定这里要从100000个数据中找出最大的100个数据,这样是为了描述方便,我们这里直接用一个数组来存储这个100000个数据,如果数据多达好几亿,则只需将这些数据放入文件中进行读写即可,这里为了描述问题方便就这样假定


步骤:

  1. 取出这些数据中前100个数据,然后用这些数据建立一个小堆;

  2. 从第101个数据开始,每读取一个数据,就与堆顶的元素进行比较,如果该数据大于堆顶的数据,则将堆顶的数据替换为该数据,并对这个小堆进行调整。

  3. 重复步骤2,等到所有数据都取完后,则留下的这个堆中的100个元素,就是我们要得到的最大的100个数。


代码如下:

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

#define N 100000  //N个数据
#define K 100     //最大或最小数据的个数


//仿函数,可以选最大的K个数,也可以选最小的K个数
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>  //默认建小堆
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个数
	{
		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;  //计算左孩子

		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;  //产生N个10000以内的随机数
	}

	Heap<int, Less<int>> get_K(randNum, K);  //小堆 选最大的K个数
	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;  //产生N个10000以内的随机数
	}

	Heap<int, Greater<int>> get_K(randNum, K);  //大堆 选最小的K个数
	get_K.CreatHeap();
	get_K.GetK(randNum, N);
	get_K.Print();
}


推荐阅读:
  1. 剑指offer:最小的k个数
  2. 找出N个数据中的最大的K个数据---堆排序

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

寻找 最大 最小

上一篇:TCP数据的传输进程

下一篇:移动互联网寒冬,程序员只能吃“青春饭”了吗

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》