按频率排序元素：同频率元素顺序不符的C++代码解决方案咨询

问题描述 #

给定一组包含重复整数的列表，需要完成以下排序任务：

• 元素按重复频率降序排列，频率最高的元素排在最前
• 若两个元素频率相同，则原数组中出现位置更靠前的元素优先

输入示例：

1 3 2 2 2 3 4 3 1

预期输出：

3 3 3 2 2 2 1 1 4

现有代码 #

#include <bits/stdc++.h> 
using namespace std;

vector<int> sortByFrequency(vector<int>& nums){
    unordered_map <int,int> mpp;
    vector <int> temp;
    for(int i=0;i<nums.size();i++)
    {
        mpp[nums[i]]++;
    }

    int max_ele;
    int max = INT_MIN;

    while(mpp.empty()==0)
    {
        for(auto it : mpp)
        {
          if (it.second > max) {
            max = it.second;
            max_ele = it.first;
          }
        }
        while(max--)
        {
            temp.push_back(max_ele);
        }
        
        mpp.erase(max_ele);
    }

    return temp;
}

int main()
{
    vector <int> arr = {1, 3, 2, 2, 2, 3, 4, 3, 1};
    vector <int> res;
    res = sortByFrequency(arr);

    for(auto it: res)
    {
        cout << it << " ";
    }
}

当前问题 #

运行上述代码后输出为：

2 2 2 3 3 3 1 1 4

该结果违反了「同频率元素保留原数组出现顺序」的规则——原数组中3比2先出现，但输出里2排在了3前面。

解决方案 #

原代码的问题在于：仅根据频率选取最大值，但unordered_map的遍历顺序是无序的，当多个元素频率相同时，无法保证按原始出现顺序优先。要解决这个问题，需要额外记录每个元素首次出现的索引，排序时先按频率降序，频率相同则按首次索引升序。

修改后的代码如下：

#include <bits/stdc++.h> 
using namespace std;

vector<int> sortByFrequency(vector<int>& nums){
    unordered_map<int, int> freq;
    unordered_map<int, int> firstOccur;
    // 记录每个元素的频率和首次出现位置
    for(int i = 0; i < nums.size(); ++i){
        if(firstOccur.find(nums[i]) == firstOccur.end()){
            firstOccur[nums[i]] = i;
        }
        freq[nums[i]]++;
    }

    // 提取所有唯一元素，用于排序
    vector<int> uniqueElements;
    for(auto& pair : freq){
        uniqueElements.push_back(pair.first);
    }

    // 自定义排序规则：先按频率降序，频率相同则按首次出现索引升序
    sort(uniqueElements.begin(), uniqueElements.end(), [&](int a, int b){
        if(freq[a] != freq[b]){
            return freq[a] > freq[b];
        } else {
            return firstOccur[a] < firstOccur[b];
        }
    });

    // 构造结果数组
    vector<int> temp;
    for(int num : uniqueElements){
        for(int i = 0; i < freq[num]; ++i){
            temp.push_back(num);
        }
    }

    return temp;
}

int main()
{
    vector <int> arr = {1, 3, 2, 2, 2, 3, 4, 3, 1};
    vector <int> res;
    res = sortByFrequency(arr);

    for(auto it: res)
    {
        cout << it << " ";
    }
}

修改说明 #

• 新增firstOccur哈希表，记录每个元素在原数组中第一次出现的索引
• 将所有唯一元素提取到uniqueElements数组中，使用自定义排序规则排序：
  • 优先比较频率，频率高的排在前面
  • 频率相同时，首次出现索引更小（原数组中出现更早）的元素排在前面
• 最后根据排序后的唯一元素和对应的频率，构造最终结果数组

运行修改后的代码，即可得到符合要求的输出：3 3 3 2 2 2 1 1 4

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