题目

给你一个整数数组 nums 和两个整数 k 和 numOperations 。

你必须对 nums 执行操作 numOperations 次。每次操作中，你可以：

选择一个下标 i ，它在之前的操作中没有被选择过。
将 nums[i] 增加范围 [-k, k] 中的一个整数。

在执行完所有操作以后，请你返回 nums 中出现 频率最高 元素的出现次数。

一个元素 x 的频率指的是它在数组中出现的次数。

示例 1：

输入：nums = [1,4,5], k = 1, numOperations = 2

输出：2

解释：

通过以下操作得到最高频率 2 ：

将 nums[1] 增加 0 ，nums 变为 [1, 4, 5] 。
将 nums[2] 增加 -1 ，nums 变为 [1, 4, 4] 。

示例 2：

输入：nums = [5,11,20,20], k = 5, numOperations = 1

输出：2

解释：

通过以下操作得到最高频率 2 ：

将 nums[1] 增加 0 。

提示：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5
0 <= k <= 10^5
0 <= numOperations <= nums.length

解题思路

共同的基础：得分公式

无论哪种解法，我们的目标都是找到一个目标值 $T$，使得最终等于 $T$ 的元素最多。

对于任何一个 T，我们能得到的最大频率（得分）都由同一个公式决定：

Score(T) = min(nA, nC + numOperations)

这里：

$n_C(T)$：原始 nums 数组中，等于 $T$ 的元素个数。
$n_A(T)$：原始 nums 数组中，落在 [T-k, T+k] 区间内的元素总数。（即所有 有潜力 变成 $T$ 的元素）
numOperations：你可用的操作次数。

这个公式的含义是，最终 $T$ 的数量有两个上限：

潜力上限 $n_A$：你最多只能有 $n_A$ 个 $T$，因为只有 $n_A$ 个元素有潜力成为 $T$。
操作上限 nC+numOperations：你本来就有 $n_C$ 个 $T$，你最多还能用操作 额外创造 numOperations 个 $T$。

两种解法的根本区别在于：如何高效地计算所有 $T$ 的 $n_A(T)$ 和 $n_C(T)$。

解法一：枚举 + 二分查找

这种解法是“以 $T$ 为中心”的。它遍历所有值得考虑的，然后对于每一个，去查询 nums 数组来计算 $n_A$ 和 $n_C$。

思路步骤：

确定 T 的范围：我们可以证明，最优的 T 一定在 nums 数组的最小值和最大值之间，即 [min(nums), max(nums)]。
- 令 $M=max(nums)−min(nums)$。根据题意， $M$ 最大约为 $10^5$。
- 令 $N=len(nums)$， N 最大也是 $10^5$。
预计算（Setup）：
- 排序：将 nums 数组排序。复杂度 $O(NlogN)$。
- 计算 $n_C$：创建一个哈希表 numCount，存储 nums 中每个元素出现的次数。复杂度 $O(N)$。
遍历并计算（Execute）：
- 我们遍历 [min(nums), max(nums)] 之间的每一个整数 $T$。这个循环执行 $M$ 次。
- 在循环内部（对于每个 $T$）：
  - 获取 $n_C(T)$：从 numCount 哈希表中直接读取，nC := numCount[T]。复杂度 $O(1)$。
  - 计算 $n_A(T)$：利用已排序的 nums 数组，使用二分查找（sort.SearchInts）来找到 [T-k, T+k] 区间内的元素数量。
    - startIdx = sort.SearchInts(nums, T-k)
    - endIdx = sort.SearchInts(nums, T+k+1)
    - nA = endIdx - startIdx。复杂度 $O(logN)$。
  - 计算得分：score = min(nA, nC + numOperations)。
  - 更新答案：maxFreq = max(maxFreq, score)。

复杂度分析：

总时间：$O(NlogN (排序))$+$O(MlogN (循环与二分))$。
由于 $N$ 和 $M$ 最大都是 $10^5$，总复杂度约为 $O((N+M)logN)$，这是完全可以接受的。

一句话总结：“对于 [min, max] 区间中的每一个目标 $T$，我都去问 nums 数组：‘你们有多少人能变成我？’”

解法二：差分数组（Sweep Line）

这种解法是“以 nums[i] 为中心”的。它遍历 nums 数组中的每一个数，让每个数 $x$ 都去给它能到达的所有目标 $T$（即 [x-k, x+k] 区间）“投一票”。最后看哪个 $T$ 得票（$n_A$）最多。

思路步骤：

确定“目标轴”：
- 所有 nums[i] 能覆盖的 T 的总范围是 [L, R]，其中 $L=min(nums)−k$，$R=max(nums)+k$。
- 令 $S=R−L+1$。这个 $S$ 的最大规模约为 $V+2K$（$V=max(nums),K=k$），最大可达 $10^5+2×10^5=3×10^5$。
创建“记分牌”数组：
- base[S]：用于存储 $n_C$。base[i] 对应目标 $T=i+L$ 的原始数量。
- cover[S]：用于存储 $n_A$。cover[i] 对应目标 $T=i+L$ 的可达数量。
- diff[S]：用于高效计算 cover 数组的差分数组。
- 为了方便，我们还需要一个 offset = -L，将 [L, R] 映射到 [0, S-1]。
计算 $n_C$ 数组（base）：
- 遍历 nums 数组（$O(N)$）。
- 对于每个数 $x$：base[x + offset]++。
计算 $n_A$ 数组（cover）：
- a. 标记差分：遍历 nums 数组（$O(N)$）。
  - 对于每个数 $x$，它能覆盖的 T 的索引范围是 [l, r]，其中 l = x-k+offset，r = x+k+offset。
  - 我们在 diff 数组上标记这个区间更新：diff[l]++，diff[r+1]--。
- b. 还原 cover：遍历 diff 数组（$O(S)$），计算前缀和。
  - cur = 0; for i = 0 to S-1: cur += diff[i]; cover[i] = cur;
  - 执行完毕后，cover[i] 就等于 $n_A(T=i+L)$。
计算最终答案：
- 遍历 cover 和 base 数组（$O(S)$）。
- 对于每个索引 i：
  - nC = base[i]
  - nA = cover[i]
  - score = min(nA, nC + numOperations)。
  - maxFreq = max(maxFreq, score)。

复杂度分析：

令 $V=max(nums),K=k$。
总时间：$O(N (遍历nums))+O(S (还原cover))+O(S (最后计算))=O(N+S)$。
$S≈V+2K$。
总复杂度为 $O(N+V+K)$。

一句话总结：“对于 nums 中的每一个数 $x$，我都让它去给 [x-k, x+k] 范围内的所有 $T$ 投一票。最后，我遍历所有 $T$，看看谁的票数（$n_A$）和原始数量（$n_C$）结合 numOperations 能得到的得分最高。”

具体代码

解法一

/**
 * 解题思路：
 * 1. 最终的目标值 T，其最优解一定在 [min(nums), max(nums)] 范围内。
 * 2. 遍历这个范围内的所有整数 T。
 * 3. 对于每个 T，计算其得分 Score(T) = min(nA, nC + numOperations)
 * - nC: 原始数组中等于 T 的元素个数。
 * - nA: 原始数组中落在 [T-k, T+k] 区间内的元素总个数。
 * 4. 为了高效计算 nA 和 nC：
 * - a. 对 nums 排序。
 * - b. 预计算 nC 到一个 map (numCount) 中。
 * - c. 使用二分查找 (sort.SearchInts) 在 O(logN) 内计算 nA。
 * 5. 返回所有 Score(T) 中的最大值。
 */
func maxFrequency(nums []int, k int, numOperations int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}

	// 1. 排序，O(N log N)
	sort.Ints(nums)

	// 2. 预计算 nC 到 map，O(N)
	numCount := make(map[int]int)
	for _, x := range nums {
		numCount[x]++
	}

	// 3. 获取 T 的枚举范围
	minNum := nums[0]
	maxNum := nums[n-1]
	
	maxFreq := 0

	// 4. 遍历 [min, max] 范围内的所有 T
	// 循环次数 M = maxNum - minNum <= 10^5
	// 复杂度 O(M log N)
	for T := minNum; T <= maxNum; T++ {
		
		// 5a. 获取 nC, O(1)
		nC := numCount[T] // map[key] 在 key 不存在时返回 0，符合逻辑

		// 5b. 计算 nA, O(log N)
		
		// 找到第一个 >= (T-k) 的位置
		startIdx := sort.SearchInts(nums, T-k)
		
		// 找到第一个 > (T+k) 的位置 (即第一个 >= T+k+1)
		endIdx := sort.SearchInts(nums, T+k+1)
		
		// nA 是落在 [T-k, T+k] 范围内的元素总数
		nA := endIdx - startIdx

		// 5c. 计算得分 Score(T)
		currentFreq := min(nA, nC+numOperations)

		// 5d. 更新答案
		maxFreq = max(maxFreq, currentFreq)
	}

	return maxFreq
}

解法二

/**
 * 解法二：差分数组（线性时间 O(N + V + K)）
 *
 * 1. 确定一个“目标轴” T，范围 [L, R]，
 * L = min(nums) - k, R = max(nums) + k。
 * 这个轴代表了所有值得考虑的目标值 T。
 * 2. 创建数组 base[] 来存储 nC(T) (原始计数)。
 * 3. 创建数组 cover[] 来存储 nA(T) (可达计数)。
 * 4. 使用差分数组 diff[] 来高效地计算 cover[]。
 * 5. 遍历 nums：
 * - 在 base[x] 处计数 (nC)。
 * - 在 diff[x-k] 和 diff[x+k+1] 处打标记 (为 nA)。
 * 6. 对 diff[] 求前缀和，还原出 cover[] 数组 (nA)。
 * 7. 遍历 base[] 和 cover[]，根据公式 Score(T) = min(nA, nC + numOps) 计算最大值。
 */
func maxFrequency(nums []int, k int, numOperations int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}

	// 1. 确定 [L, R] 范围
	// minV, maxV 限制了 T 的有效计算范围
	minV, maxV := nums[0], nums[0]
	for _, x := range nums {
		if x < minV {
			minV = x
		}
		if x > maxV {
			maxV = x
		}
	}

	// L 和 R 定义了我们需要关心的“目标轴” T 的总范围
	L := minV - k
	R := maxV + k
	
	// C++ 中可以 L < 0，Go 中为了简化，
	// 可以将所有坐标平移到非负数。
	// 但更简单的做法是直接使用 L 作为偏移量
	offset := -L // 偏移量，使得索引 0 对应 T = L
	size := R - L + 1 // "目标轴"的总长度

	// 2. 创建 base 数组 (存储 nC)
	// base[i] 存储的是 T = i+L 的原始数量
	base := make([]int, size)

	// 3. 创建 diff 数组 (为 nA 做准备)
	// diff[i] 对应 T = i+L
	// 我们需要 size+1 的空间来标记 r+1
	diff := make([]int, size+1) 

	// 4. 遍历 nums，填充 base 和 diff
	for _, x := range nums {
		// 4a. 填充 base (nC)
		base[x+offset]++

		// 4b. 填充 diff (为 nA 打标记)
		// x 可以覆盖的目标 T 范围是 [x-k, x+k]
		// 对应的索引范围是 [l, r]
		l := x - k + offset
		r := x + k + offset

		// 区间开始标记
		diff[l]++ 
		
		// 区间结束标记
		diff[r+1]--
		
	}

	// 5. 对 diff 求前缀和，还原出 cover 数组 (nA)
	// cover[i] 存储 T = i+L 的可达总数 (nA)
	// 我们可以在一个循环内同时完成还原和计算答案
	
	ans := 0
	curCover := 0 // 当前的前缀和，即 cover[i]
	
	// 6. 遍历“目标轴”，计算所有 T 的得分
	for i := 0; i < size; i++ {
		// 6a. 还原 nA
		curCover += diff[i]
		nA := curCover
		
		// 6b. 获取 nC
		nC := base[i]
		
		// 6c. 计算得分 Score(T = i+L)
		// cand = nC + numOperations
		cand := nC + numOperations
		
		// score = min(nA, nC + numOperations)
		if cand > nA {
			cand = nA
		}
		
		// 6d. 更新答案
		if cand > ans {
			ans = cand
		}
	}
	
	return ans
}

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

beautifulremi

题目

解题思路

共同的基础：得分公式

解法一：枚举 + 二分查找

解法二：差分数组（Sweep Line）

具体代码

解法一

解法二