时间轴

2025-10-21

init

题目：

P3346 执行操作后元素的最高频率 I

https://leetcode.cn/problems/maximum-frequency-of-an-element-after-performing-operations-i/description/?envType=daily-question&envId=2025-10-21

WA

先看 WA 的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <vector>
#include <unordered_map>
#include <algorithm>

using std::vector;
using std::unordered_map;

class Solution {
    public:
	int maxFrequency(vector<int> &nums, int k, int numOperations)
	{
		int n = nums.size();
		int i;
		int left_bound, right_bound;
		int max_val;
		int res = 0;
		unordered_map<int, int> umap;
		for (i = 0; i < n; i++) {
			umap[nums[i]]++;
		}
		std::sort(nums.begin(), nums.end());
		nums.erase(std::unique(nums.begin(), nums.end()), nums.end());
		n = nums.size();
		for (i = 0; i < n; i++) {
			max_val = 0;
			left_bound = i - 1;
			while (left_bound >= 0 &&
			       nums[left_bound] >= nums[i] - k) {
				max_val += umap[left_bound];
				left_bound--;
			}

			right_bound = i + 1;
			while (right_bound < n &&
			       nums[right_bound] <= nums[i] + k) {
				max_val += umap[right_bound];
				right_bound++;
			}
			if (max_val <= numOperations) {
				res = std::max(res, max_val + umap[nums[i]]);
			} else {
				res = std::max(res,
					       numOperations + umap[nums[i]]);
			}
		}
		return res;
	}
};

对于输入

1
2
3
nums = [5,64]
k = 42
numOperations = 2

上面的代码是 WA 的，因为上面的代码只把最终频率最大的众数，我们称为目标众数的枚举范围只限定在 nums 中的值了。实际上，对于每个数都可以进行一次 operation，两个数如果都进行一次 operation 后相等也是符合要求的。

AC

上面 WA 的原因主要是我们没有枚举完整，对于一个值 nums[i]，我们要找 nums[i]中值处于[nums[i]-k,nums[i]+k]之间的值，这样的值通过一次 operation 就能变成目标众数。但是仅仅考虑 nums[i]是不正确的，因为 nums[i]也可以通过一次 operation 变成[nums[i]-k,nums[i]+k]之间的任何一个值作为目标众数。
那么我们还要将 num[i]待选目标众数通过一次 operation 得到的所有值都作为目标众数枚举一遍吗？答案是否定的。

核心概念

  • 排序数组 nums
  • 每个元素的可操作区间：[nums[i]-k, nums[i]+k]
  • 枚举目标众数 val → 计算能变成 val 的元素数量

定义窗口 [val-k, val+k]：

  • 左边界 l：窗口包含的最左元素
  • 右边界 r：窗口包含的最右元素
  • range_size = r - l + 1

最大频率：

关键观察

只有当窗口的左右边界 l 或 r 发生变化时，range_size 才会变化 → f_i 才可能变大

  • 假设 val ∈ [nums[r]-k, nums[r+1]-k)：
    • r 不变
    • l 不变
    • range_size 恒定 → f_i 不变
  • 区间内部的所有 val 不会增加最大频率 → 无需枚举

临界点分析

窗口边界变化的临界点：

  1. 左边界 l 变化：val - k = nums[i]（左边元素刚好进入/离开窗口）
  2. 右边界 r 变化：val + k = nums[i]（右边元素刚好进入/离开窗口）

也就是说，只有当 val 等于某个 nums[i] ± k 或 nums[i] 本身，窗口边界会发生变化。

  • val = nums[i] → 对应窗口覆盖 nums[i] 本身
  • val = nums[i] - k → 窗口左边界刚好覆盖 nums[i]
  • val = nums[i] + k → 窗口右边界刚好覆盖 nums[i]

这三个值就是 所有可能改变窗口范围的临界点

综上：我们只需要枚举边界值即可，即枚举{nums[i]-k , nums[i], num[i] +k}。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <vector>
#include <unordered_map>
#include <algorithm>

using std::vector;
using std::unordered_map;

class Solution {
    public:
	int maxFrequency(vector<int> &nums, int k, int numOperations)
	{
		int n = nums.size();
		int i;
		int range_size;
		int res = 0;
		unordered_map<int, int> umap;
		for (i = 0; i < n; i++) {
			umap[nums[i]]++;
		}
		std::sort(nums.begin(), nums.end());

		n = nums.size();
		// 0 <= numOperations <= nums.length
		for (i = 0; i < n; i++) {
			for (int val : { nums[i] - k, nums[i], nums[i] + k }) {
				// 要枚举的值不在范围内
				if (val < nums.front() || val > nums.back()) {
					// 如果val比nums最小值还小，没有意义，因为任何一个值能通过操作变成这个val，那么肯定也可以变成nums的最小值，那么为什么不用最小值作为目标众数呢？
					continue;
				}
				// range {x in nums[i] && x in {val-k..val+k}}
				range_size =
					std::upper_bound(nums.begin(),
							 nums.end(), val + k) -
					std::lower_bound(nums.begin(),
							 nums.end(), val - k);

				// 最终能把某个值变成出现次数最多的频率 = 原来这个值的出现次数 +
				// 通过操作可以变成这个值的次数,但不能超过窗口内可转换到的数量
				res = std::max(
					res, std::min(numOperations + umap[val],
						      range_size));
			}
		}
		return res;
	}
};

int main()
{
	vector<int> nums = { 999999997, 999999999, 999999999 };
	Solution S;
	int k = 999999999;
	int numOperations = 2;
	S.maxFrequency(nums, k, numOperations);
}