Kimi LeetCode 3347. 执行操作后元素的最高频率 II C语言实现
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, x+k]` 范围内的任意值。对于某个目标值 `T`：
- 能变成 `T` 的元素个数 = 满足 `x-k ≤ T ≤ x+k` 的元素个数
- 其中原本就等于 `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 (确保存在), num+k+1 (-1)
// 但 num 可能已经存在，所以最多 3*numsSize 个条目
// 实际上 num-k 和 num+k+1 可能重复，我们用数组收集后排序合并
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;
// 标记左端点 +1
diff[diff_count].key = left;
diff[diff_count].val = 1;
diff_count++;
// 标记右端点+1处 -1
diff[diff_count].key = right;
diff[diff_count].val = -1;
diff_count++;
}
// 确保每个原始值在 diff 中存在（值为0）
for (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`（开始覆盖），在 `num+k+1` 处 `-1`（结束覆盖）。同时确保每个原始值在 diff 中存在
排序合并 将所有差分条目按坐标排序，合并相同坐标的值
前缀和计算 遍历合并后的差分数组，`cover` 表示当前坐标被多少个元素的覆盖范围包含
频率计算 `min(cover, original + numOperations)`：覆盖数受限于"原始个数+可操作次数"
二分查找 用二分查找在 `freq_keys` 中查找当前坐标的原始频率
---
复杂度分析
- 时间复杂度：`O(n log n)`，主要来自排序操作（排序 nums、排序 diff）
- 空间复杂度：`O(n)`，用于存储频率数组和差分数组
---
示例验证
示例 1：`nums = [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}`
- 遍历：
- `x=0`: cover=1, original=0 → `min(1, 0+2)=1`
- `x=1`: cover=1, original=1 → `min(1, 1+2)=1`
- `x=3`: cover=1, original=0 → `min(1, 0+2)=1`
- `x=4`: cover=2, original=1 → `min(2, 1+2)=2` ✓
- `x=5`: cover=2, original=1 → `min(2, 1+2)=2`
- `x=6`: cover=1, original=0 → `min(1, 0+2)=1`
- 答案 = 2
示例 2：`nums = [5,11,20,20], k = 5, numOperations = 1`
- 元素 5 覆盖 `[0,10]`，11 覆盖 `[6,16]`，20 覆盖 `[15,25]`（两个20）
- 在 `x=20` 处：cover=2（两个20都能覆盖20），original=2 → `min(2, 2+1)=2` ✓
- 答案 = 2