#include<iostream>

#include<vector>

#include<unordered_map>

using namespace std;

// 计数排序，通过记录所有元素出现的次数来实现O(n)的排序算法

// 以最简单的正整数数据为例：

vector<int> JiShuSort(vector<int>&a, bool asc=true) {

    int n = a.size(), maxData = 0;

    //找到最大元素（每个元素都是正整数）

    for (int i = 0; i < n; i++) {

        maxData = max(maxData, a[i]);

    }

    // 数据都是正整数，最多有从1到maxData共maxData种数据，所以空间只用开辟这么大

    vector<int>data2num(maxData + 1, 0);

    // 记录所有数据出现的次数，进行从maxData种数据到出现次数num的映射 data to num

    for (int i = 0; i < n; i++) {

        data2num[a[i]]++;

    }

    // 获得排序结果

    vector<int> ans;

    if (asc) {      //递增顺序就从前向后遍历

        for (int i = 1; i <= maxData; i++) {

            for (int j = 0; j < data2num[i]; j++) {

                ans.push_back(i);

            }

        }

    }

    else {          //递减顺序就从后向前遍历

        for (int i = maxData; i > 0; i--) {

            for (int j = 0; j < data2num[i]; j++) {

                ans.push_back(i);

            }

        }

    }

    return ans;

}

// 打印n个字符串中出现次数最多的前N个字符串，TOP N 热词算法

// n个字符串共有cnt种不同的字符串

// 时间复杂度O(3*n + 2*cnt + N) = O(n)

void PrintTopN(vector<string>& a, int N) {

    cout << "-----------the Top " << N << " hot words is belowe--------------\n";

    unordered_map<string, int> string2id;  //hash表对新key值的默认value值为0

    int n = a.size(), cnt = 0;

    // 对cnt个不同的字符串进行hash映射，映射到[1,cnt]

    for (int i = 0; i < n; i++) {

        if (string2id[a[i]] == 0)string2id[a[i]] = ++cnt;

    }

    // 进行id到string的反向映射

    vector<string>id2string(cnt + 1);

    for (int i = 0; i < n; i++) {

        id2string[string2id[a[i]]] = a[i];

    }

    // 记录cnt个字符串出现的次数，第i个字符串出现num[i-1]次

    vector<int>id2num(cnt + 1);

    for (int i = 0; i < n; i++) {

        id2num[string2id[a[i]]]++;

    }

    // 找到最大出现次数

    int maxNum = 0;

    for (int i = 1; i <= cnt; i++)

        maxNum = max(maxNum, id2num[i]);

    // 记录每个出现次数对应的字符串id

    vector<vector<int>>num2id(maxNum + 1, vector<int>());

    for (int i = 1; i <= cnt; i++) {

        num2id[id2num[i]].push_back(i);

    }

    // 逆序打印top N

    for (int i = maxNum; i > 0; i--) {

        for (int x : num2id[i]) {

            if (N-- == 0)return;

            cout << id2string[x] << '\n';

        }

    }

}

int main() {

    string a[11] = { "one","two","three","four","five","six","steven","eight","nine","ten","eleven" };

    vector<string> strData;

    vector<int> intData;

    // 让strData中是1个“one”，2个“two”，...， 11个“eleven”

    // 让intData中是1个1，2个2，...，11个11

    for (int i = 0; i < 11; i++) {

        for (int j = 0; j <= i; j++) {

            strData.push_back(a[i]);

            intData.push_back(i + 1);

        }

    }

    // 获得intData的递减排序结果

    vector<int> ans = JiShuSort(intData, false);

    cout << "---------------下面是intData递减排序后的数据---------------\n";

    for (int x:ans) {

        cout << x << '\n';

    }

    // 获得intData的递增排序结果，asc默认是true

    ans = JiShuSort(intData);

    cout << "---------------下面是intData递增排序后的数据---------------\n";

    for (int x : ans) {

        cout << x << '\n';

    }

    //打印strData中的top 10 热词

    PrintTopN(strData, 10);

    return 0;

}