C++中如何按数组元素顺序输出unordered_map统计的元素频率？

你当前使用的unordered_map是基于哈希表实现的容器，本身不保留元素的插入顺序，所以遍历输出的顺序是不确定的，和你期望的原数组首次出现顺序自然不一致。

这是最容易实现的方案，只需要在原代码基础上做少量修改：

• 第一遍遍历正常统计所有元素的出现次数
• 第二遍遍历原数组，搭配额外的哈希集合控制只输出一次每个元素的统计结果

修改后的完整代码如下：

#include<bits/stdc++.h>

using namespace std;

void three_freq(int arr[], int n){
    unordered_map<int, int> m;
    // 第一遍遍历统计次数
    for(int i=0;i<n;i++){
        m[arr[i]]++;
    }
    unordered_set<int> printed; // 记录已经输出过的元素
    // 第二遍遍历原数组，按首次出现顺序输出
    for(int i=0;i<n;i++){
        if(printed.find(arr[i]) == printed.end()){
            cout<<arr[i]<<":"<<m[arr[i]]<<"\n";
            printed.insert(arr[i]);
        }
    }
}

int main(){
    int arr[] = {5, 2,4,2,3,5,1};
    int n = sizeof(arr)/ sizeof(arr[0]);
    three_freq(arr, n);
    return 0;
}

该方案时间复杂度仍为O(n)，和原代码一致，不会有明显性能损失。

如果数组重复元素非常多，不想二次遍历整个数组，可以在统计次数的时候，同步用vector记录首次出现的元素：

void three_freq(int arr[], int n){
    unordered_map<int, int> m;
    vector<int> order;
    for(int i=0;i<n;i++){
        if(m.find(arr[i]) == m.end()){
            order.push_back(arr[i]);
        }
        m[arr[i]]++;
    }
    // 直接遍历顺序vector输出即可
    for(auto num : order){
        cout<<num<<":"<<m[num]<<"\n";
    }
}

这种方案在重复元素多的场景下效率更高，遍历输出的次数等于不同元素的个数。

内容的提问来源于stack exchange，提问作者Anim