LeetCode 1838题：最高频元素频率求解代码错误排查

题目描述 #

元素的频率是其在数组中出现的次数。
给定整数数组nums和整数k，每次操作可选择数组中的一个索引并将对应元素加1。
返回执行最多k次操作后，元素的最大可能频率。

我的代码 #

int checkfreq(vector<int> nums, int k, int i)
{
    int counter = 0;
    int el = nums[i];
    while (k != 0 && i > 0)
    {
        --i;
        while (nums[i] != el && k > 0 && i >= 0)
        {
            ++nums[i];
            --k;
        }
    }
    counter = count(nums.begin(), nums.end(), el);
    return counter;
}

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        vector<int> nums2 = nums;
        auto distinct = unique(nums2.begin(), nums2.end());
        nums2.resize(distance(nums2.begin(), distinct));
        int xx = nums.size() - 1;
        int counter = checkfreq(nums, k, xx);
        for (int i = nums2.size() - 2; i >= 0; --i)
        {
            --xx;
            int temp = checkfreq(nums, k, xx);
            if (temp > counter)
                counter = temp;
        }
   
        return counter;
    }
};

失败的测试用例 #

输入 #

nums = [9968,9934,9996,9928,9934,9906,9971,9980,9931,9970,9928,9973,9930,9992,9930,9920,9927,9951,9939,9915,9963,9955,9955,9955,9933,9926,9987,9912,9942,9961,9988,9966,9906,9992,9938,9941,9987,9917,10000,9919,9945,9953,9994,9913,9983,9967,9996,9962,9982,9946,9924,9982,9910,9930,9990,9903,9987,9977,9927,9922,9970,9978,9925,9950,9988,9980,9991,9997,9920,9910,9957,9938,9928,9944,9995,9905,9937,9946,9953,9909,9979,9961,9986,9979,9996,9912,9906,9968,9926,10000,9922,9943,9982,9917,9920,9952,9908,10000,9914,9979,9932,9918,9996,9923,9929,9997,9901,9955,9976,9959,9995,9948,9994,9996,9939,9977,9977,9901,9939,9953,9902,9926,9993,9926,9906,9914,9911,9901,9912,9990,9922,9911,9907,9901,9998,9941,9950,9985,9935,9928,9909,9929,9963,9997,9977,9997,9938,9933,9925,9907,9976,9921,9957,9931,9925,9979,9935,9990,9910,9938,9947,9969,9989,9976,9900,9910,9967,9951,9984,9979,9916,9978,9961,9986,9945,9976,9980,9921,9975,9999,9922]
k = 1524

输出 #

• 预期结果：81
• 我的代码返回：79

错误原因分析 #

1. 遍历不同元素时的索引定位错误 #

通过nums2获取去重后的元素列表后，仅用--xx来定位当前测试元素的位置是错误的。原数组排序后可能存在大量相同元素，xx递减后仍可能指向原数组中属于上一个（更大的）元素的位置，而非当前nums2[i]对应的最后一个元素位置。这导致你没有真正测试每个不同元素作为目标值的情况，直接错过最优解。

2. checkfreq函数未处理第一个元素 #

checkfreq的外层循环条件是while(k != 0 && i > 0)，当i递减到0时循环直接终止，不会处理nums[0]。即使此时k还有剩余，也无法将nums[0]加到目标值el，导致统计的频率偏小。

3. 逐次加1的低效逻辑（非直接错误，但影响性能） #

在checkfreq中，通过循环逐个将元素加1到目标值，而非直接计算所需操作次数（el - nums[i]）并一次性扣除对应的k值。虽然这不会导致逻辑错误，但在大数据量下会严重降低效率，甚至可能超时。

修正建议 #

• 正确定位每个去重元素的最后位置：不要通过xx--获取位置，而是遍历原数组，找到每个nums2[i]在原数组中的最后一个索引。
• 修复checkfreq的循环条件：将外层循环条件改为while(k > 0 && i >= 0)，确保第一个元素也能被处理。
• 优化操作次数计算：直接计算当前元素到目标值的差值diff = el - nums[i]，如果diff <= k，则扣除k -= diff并将nums[i]设为el；否则，只加k次并终止循环，避免逐次加1的低效操作。

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