LeetCode 题解工作台
执行操作后元素的最高频率 I
给你一个整数数组 nums 和两个整数 k 和 numOperations 。 你必须对 nums 执行 操作 numOperations 次。每次操作中，你可以： 选择一个下标 i ，它在之前的操作中 没有 被选择过。 将 nums[i] 增加范围 [-k, k] 中的一个整数。 在执行完所有操作…
5
题型
5
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
根据题目描述，对于数组 中的每个元素 ，我们可以将其变为 $[x-k, x+k]$ 范围内的任意整数。我们希望通过对 中的若干元素进行操作，使得某个整数在数组中出现的次数最多。 题目可以转化为，将每个元素 对应的区间 $[x-k, x+k]$ 的所有元素进行合并，找出合并后区间中包含最多原始元素的整数。这可以通过差分数组来实现。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个整数数组 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 <= 1051 <= nums[i] <= 1050 <= k <= 1050 <= numOperations <= nums.length
解题思路
方法一：差分
根据题目描述，对于数组 中的每个元素 ，我们可以将其变为 范围内的任意整数。我们希望通过对 中的若干元素进行操作，使得某个整数在数组中出现的次数最多。
题目可以转化为，将每个元素 对应的区间 的所有元素进行合并，找出合并后区间中包含最多原始元素的整数。这可以通过差分数组来实现。
我们使用一个字典 来记录差分数组。对于每个元素 ，我们在差分数组中执行以下操作：
- 在位置 处加 ，表示从这个位置开始，有一个新的区间开始。
- 在位置 处减 ，表示从这个位置开始，有一个区间结束。
- 在位置 处加 ，确保位置 存在于差分数组中，方便后续计算。
同时，我们还需要记录每个元素在原始数组中出现的次数，使用字典 来实现。
接下来，我们对差分数组进行前缀和计算，得到每个位置上有多少个区间覆盖。对于每个位置 ，我们计算其覆盖的区间数 。接下来分类讨论：
- 如果 在原始数组中出现过，对于 自身的操作，没有意义，因此会有 个其他的元素可以通过操作变为 ，但最多只能操作 次，所以该位置的最大频率为 。
- 如果 在原始数组中没有出现过，那么最多只能通过操作 次将其他元素变为 ，因此该位置的最大频率为 。
综合以上两种情况，我们可以统一表示为 。
最后，我们遍历所有位置，计算出每个位置的最大频率，并取其中的最大值作为答案。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def maxFrequency(self, nums: List[int], k: int, numOperations: int) -> int:
cnt = defaultdict(int)
d = defaultdict(int)
for x in nums:
cnt[x] += 1
d[x] += 0
d[x - k] += 1
d[x + k + 1] -= 1
ans = s = 0
for x, t in sorted(d.items()):
s += t
ans = max(ans, min(s, cnt[x] + numOperations))
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ability to implement binary search over a dynamic range of values.
- question_mark
Understanding the sliding window technique to optimize operations.
- question_mark
Proficiency in combining sorting and prefix sums for optimization.
常见陷阱
外企场景- error
Failing to account for edge cases such as small arrays or zero operations.
- error
Not efficiently handling the sliding window bounds while calculating required operations.
- error
Overlooking the sorting step which may impact the overall efficiency of the solution.
进阶变体
外企场景- arrow_right_alt
Introducing constraints on the number of operations for different elements.
- arrow_right_alt
Handling multiple arrays with different lengths in the same problem.
- arrow_right_alt
Changing the operation from addition to subtraction, making the problem more complex.