in Coding c c++ 算法与数据结构 ~ read.

[算法]计算输入数据的出现频率

一个比较巧妙的方法,将输入的数据按照出现频率输出
每次看都记不住,翻出来再看就像是第一次看到一样,特此记录,保留

/*
* 输入数据,按照出现频率输出
* a:输入的元素
* n:数组大小
* k:频率前三
* */

#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;


template<typename T>
class KeyVal
{
public:
	KeyVal(int k, T v) :key(k), value(v) {}
	bool operator<(const KeyVal<T> &a) const
	{
		return key > a.key;
	}

	int key;
	T value;
};

class Cal {
public:
	Cal() {};
	~Cal() {};
public:
	template<typename T>
	void read(T a[], int &n, int &k) {
		cin >> n >> k;
		for (int i = 1;i <= n;++i)
			cin >> a[i];
	}

	template<typename T>
	void solve(T a[], int n, int k) {
		unordered_map <T, int> mp;    // T存入map, 按出现次数计算int
		typename unordered_map <T, int>::iterator it;
		//vector< pair<int, T> > tmp;
		vector< KeyVal<T> > tmp;

		for (int i = 1;i <= n;++i)
			++mp[a[i - 1]];   // 将a[]中的元素作为key存入, 相同key的value会被++

		for (it = mp.begin();it != mp.end();++it)
			tmp.push_back(KeyVal<T>(it->second, it->first));

		//sort(tmp.begin(), tmp.end(), cmp);
		sort(tmp.begin(), tmp.end(), less< KeyVal<T> >());
		for (int i = 0;i < k;++i)
			cout << tmp[i].key << ":" << tmp[i].value << endl;
	}
};

int main() {
	//int a[] = {123,123,123,66,66,55,55,33};
	//char a[] = {'a','a','a','r','r','b','b','c'};
	string a[] = { "aasd","aasd","aasd","aa","aa","bb","bb","cc" };
	int n = 8, k = 3;
	Cal* cal = new Cal();
	//read(a, n, k);
	cal->solve(a, n, k);
	system("PAUSE");
	return 0;
}