C++递归处理引用传递vector的LeetCode高频元素问题求助

要解决递归分支中修改vector不互相干扰的问题，核心用回溯思想：在递归分支中修改数组元素后，等递归调用返回时，再将元素恢复原值，这样每个分支的修改只会作用于当前递归路径，不会影响其他分支。

具体实现思路 #

• 先对数组排序（可选，但能减少重复操作，提升递归效率）：排序后可以更有针对性地选择要提升的元素，避免无意义的递归分支。
• 设计辅助递归函数：参数包含原数组引用、剩余操作次数k、用于记录最大频数的引用变量。
• 递归分支处理：遍历数组元素，尝试将当前元素加1（若还有剩余操作次数），递归调用后再将元素减1恢复状态，进入下一个分支。
• 实时更新最大频数：每次递归时计算当前数组的元素频数，更新全局记录的最大频数。

代码示例 #

#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

class Solution {
private:
    void backtrack(vector<int>& nums, int k, int& max_freq) {
        // 计算当前数组的元素频数，更新最大频数
        unordered_map<int, int> freq_map;
        int current_max = 0;
        for (int num : nums) {
            freq_map[num]++;
            current_max = max(current_max, freq_map[num]);
        }
        max_freq = max(max_freq, current_max);

        // 终止条件：无剩余操作次数
        if (k == 0) {
            return;
        }

        // 遍历每个元素，尝试执行加1操作
        for (int i = 0; i < nums.size(); i++) {
            // 剪枝：若当前元素已是最大值，加1无法提升现有频数，跳过该分支
            bool is_current_max = true;
            for (int num : nums) {
                if (num > nums[i]) {
                    is_current_max = false;
                    break;
                }
            }
            if (is_current_max) continue;

            // 修改元素，进入递归分支
            nums[i]++;
            backtrack(nums, k - 1, max_freq);
            // 回溯，恢复元素原值
            nums[i]--;
        }
    }
public:
    int maxFrequency(vector<int>& nums, int k) {
        int max_freq = 0;
        sort(nums.begin(), nums.end()); // 排序优化递归效率
        backtrack(nums, k, max_freq);
        return max_freq;
    }
};

注意事项 #

• 上述递归解法时间复杂度为指数级，对于长度较大的数组（如长度>10）会超时，因为递归分支过多且每次都要遍历数组计算频数。
• 这道题的最优解法是滑动窗口，可以在O(n log n)时间复杂度内完成，但上述代码可满足递归回溯思想的学习需求。

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