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