LeetCode 3347. 执行操作后元素的最高频率 II — C 语言实现题目回顾给定整数数组 nums 和两个整数 k、numOperations。可以执行最多 numOperations 次操作每次选择一个未被选过的下标 i将 nums[i] 增加 [-k, k] 范围内的任意整数。求操作后数组中最高频率元素的出现次数。关键约束II 与 I 的区别- nums[i] 最大可达 10⁹I 中是 10⁵- k 最大可达 10⁹因此不能用数组遍历值域需要使用差分数组离散化或排序双指针来优化。---核心思路差分数组离散化每个元素 x 可以变成 [x-k, xk] 范围内的任意值。对于某个目标值 T- 能变成 T 的元素个数 满足 x-k ≤ T ≤ xk 的元素个数- 其中原本就等于 T 的元素不需要消耗操作次数- 实际需要操作次数 能变成T的元素个数 - 原本等于T的元素个数- 最终频率 原本等于T的元素个数 min(实际需要操作次数, numOperations)关键洞察最优的 T 一定出现在某个 nums[i]-k、nums[i] 或 nums[i]k 处。因此可以用差分数组在离散坐标上标记每个元素的覆盖范围然后通过前缀和统计每个候选点的覆盖数。---C 语言代码实现c#include stdlib.h// 用于 qsort 的比较函数static int cmp_int(const void *a, const void *b) {int x *(const int *)a;int y *(const int *)b;if (x y) return -1;if (x y) return 1;return 0;}// 用于 qsort 比较结构体按坐标排序typedef struct {long long key; // 坐标值用 long long 防止溢出int val; // 差分值} DiffEntry;static int cmp_entry(const void *a, const void *b) {DiffEntry *ea (DiffEntry *)a;DiffEntry *eb (DiffEntry *)b;if (ea-key eb-key) return -1;if (ea-key eb-key) return 1;return 0;}int maxFrequency(int* nums, int numsSize, int k, int numOperations) {// 1. 统计每个数字的原始出现频率// 先对 nums 排序方便统计频率int *sorted_nums (int *)malloc(numsSize * sizeof(int));for (int i 0; i numsSize; i) {sorted_nums[i] nums[i];}qsort(sorted_nums, numsSize, sizeof(int), cmp_int);// 用数组存储 (值, 频率) 对// 最多 numsSize 个不同的值long long *freq_keys (long long *)malloc(numsSize * sizeof(long long));int *freq_vals (int *)malloc(numsSize * sizeof(int));int freq_count 0;for (int i 0; i numsSize; ) {int j i;while (j numsSize sorted_nums[j] sorted_nums[i]) {j;}freq_keys[freq_count] sorted_nums[i];freq_vals[freq_count] j - i;freq_count;i j;}// 2. 构建差分数组// 每个元素产生 3 个关键点num-k (1), num (确保存在), numk1 (-1)// 但 num 可能已经存在所以最多 3*numsSize 个条目// 实际上 num-k 和 numk1 可能重复我们用数组收集后排序合并int max_diff_size numsSize * 3;DiffEntry *diff (DiffEntry *)malloc(max_diff_size * sizeof(DiffEntry));int diff_count 0;for (int i 0; i numsSize; i) {long long num nums[i];long long left num - (long long)k;long long right num (long long)k 1;// 标记左端点 1diff[diff_count].key left;diff[diff_count].val 1;diff_count;// 标记右端点1处 -1diff[diff_count].key right;diff[diff_count].val -1;diff_count;}// 确保每个原始值在 diff 中存在值为0for (int i 0; i freq_count; i) {diff[diff_count].key freq_keys[i];diff[diff_count].val 0;diff_count;}// 3. 按坐标排序差分数组并合并相同坐标的值qsort(diff, diff_count, sizeof(DiffEntry), cmp_entry);// 合并相同 key 的条目DiffEntry *merged (DiffEntry *)malloc(diff_count * sizeof(DiffEntry));int merged_count 0;for (int i 0; i diff_count; ) {long long key diff[i].key;int sum 0;while (i diff_count diff[i].key key) {sum diff[i].val;i;}merged[merged_count].key key;merged[merged_count].val sum;merged_count;}// 4. 计算前缀和遍历每个点求最大频率int ans 0;int cover 0; // 当前前缀和for (int i 0; i merged_count; i) {cover merged[i].val;long long x merged[i].key;// 查找 x 在 freq 中的原始频率int original 0;// 二分查找int lo 0, hi freq_count - 1;while (lo hi) {int mid lo (hi - lo) / 2;if (freq_keys[mid] x) {original freq_vals[mid];break;} else if (freq_keys[mid] x) {lo mid 1;} else {hi mid - 1;}}// 计算当前坐标能达到的最大频率int possible cover;int limit original numOperations;int current possible limit ? possible : limit;if (current ans) {ans current;}}// 释放内存free(sorted_nums);free(freq_keys);free(freq_vals);free(diff);free(merged);return ans;}---代码详解步骤 说明统计频率 先对 nums 排序然后遍历统计每个不同值的频率存储在 freq_keys值和 freq_vals频率中差分标记 对每个 num在 num-k 处 1开始覆盖在 numk1 处 -1结束覆盖。同时确保每个原始值在 diff 中存在排序合并 将所有差分条目按坐标排序合并相同坐标的值前缀和计算 遍历合并后的差分数组cover 表示当前坐标被多少个元素的覆盖范围包含频率计算 min(cover, original numOperations)覆盖数受限于原始个数可操作次数二分查找 用二分查找在 freq_keys 中查找当前坐标的原始频率---复杂度分析- 时间复杂度O(n log n)主要来自排序操作排序 nums、排序 diff- 空间复杂度O(n)用于存储频率数组和差分数组---示例验证示例 1nums [1,4,5], k 1, numOperations 2- 元素 1 覆盖 [0, 2]元素 4 覆盖 [3, 5]元素 5 覆盖 [4, 6]- 差分标记{0:1, 3:-1, 3:1, 6:-1, 4:1, 7:-1, 1:0, 4:0, 5:0}- 排序合并后{0:1, 1:0, 3:0, 4:1, 5:0, 6:-1, 7:-1}- 遍历- x0: cover1, original0 → min(1, 02)1- x1: cover1, original1 → min(1, 12)1- x3: cover1, original0 → min(1, 02)1- x4: cover2, original1 → min(2, 12)2 ✓- x5: cover2, original1 → min(2, 12)2- x6: cover1, original0 → min(1, 02)1- 答案 2示例 2nums [5,11,20,20], k 5, numOperations 1- 元素 5 覆盖 [0,10]11 覆盖 [6,16]20 覆盖 [15,25]两个20- 在 x20 处cover2两个20都能覆盖20original2 → min(2, 21)2 ✓- 答案 2