LeetCode按频率递增排序数组题stl_vector.h溢出运行时错误求解

错误原因 #

你遇到的报错是vector越界访问导致的未定义行为，核心问题出在统计频率的逻辑：

• 你初始化了大小为n（输入数组nums的长度）的vector<pair<int,int>> v，但直接用nums[i]作为下标访问v的元素。该题nums的元素取值范围是[-100, 100]，负数下标访问vector本身就是非法操作，就算元素为正，只要数值大于等于n也会超出vector的合法访问范围，直接触发内存地址溢出报错。
• 后续逻辑也存在问题：你创建的v大小为n，但实际需要存储的是不同数值和对应频率的配对，数量远小于n，排序时会把大量未赋值的空pair也参与排序，最终输出结果也不符合题目要求。

修复方案 #

用哈希表统计频率规避下标问题，再按规则排序构造结果即可：

1. 用unordered_map统计每个数值的出现频率
2. 将所有<频率, 数值>配对存入待排序数组
3. 按原有规则排序：频率低的在前，频率相同则数值大的在前
4. 遍历排序后的数组，按频率将数值推入结果数组

修正后完整代码 #

class Solution {
public:
    static bool cmp(pair<int,int> a, pair<int,int> b){
        if(a.first < b.first) return true;
        if(a.first == b.first && a.second > b.second) return true;
        return false;
    }
    vector<int> frequencySort(vector<int>& nums) {
        unordered_map<int, int> cnt;
        for (int num : nums) {
            cnt[num]++;
        }
        vector<pair<int, int>> v;
        for (auto& p : cnt) {
            v.emplace_back(p.second, p.first);
        }
        sort(v.begin(), v.end(), cmp);
        vector<int> res;
        for (auto& p : v) {
            for (int i = 0; i < p.first; i++) {
                res.push_back(p.second);
            }
        }
        return res;
    }
};

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