题目描述
给你一个整数数组 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 ：
提示：
1 <= nums.length <= 1051 <= nums[i] <= 1050 <= k <= 1050 <= numOperations <= nums.length
解法
方法一：差分
根据题目描述，对于数组 \(\textit{nums}\) 中的每个元素 \(x\)，我们可以将其变为 \([x-k, x+k]\) 范围内的任意整数。我们希望通过对 \(\textit{nums}\) 中的若干元素进行操作，使得某个整数在数组中出现的次数最多。
题目可以转化为，将每个元素 \(x\) 对应的区间 \([x-k, x+k]\) 的所有元素进行合并，找出合并后区间中包含最多原始元素的整数。这可以通过差分数组来实现。
我们使用一个字典 \(d\) 来记录差分数组。对于每个元素 \(x\)，我们在差分数组中执行以下操作：
- 在位置 \(x-k\) 处加 \(1\)，表示从这个位置开始，有一个新的区间开始。
- 在位置 \(x+k+1\) 处减 \(1\)，表示从这个位置开始，有一个区间结束。
- 在位置 \(x\) 处加 \(0\)，确保位置 \(x\) 存在于差分数组中，方便后续计算。
同时，我们还需要记录每个元素在原始数组中出现的次数，使用字典 \(cnt\) 来实现。
接下来，我们对差分数组进行前缀和计算，得到每个位置上有多少个区间覆盖。对于每个位置 \(x\)，我们计算其覆盖的区间数 \(s\)。接下来分类讨论：
- 如果 \(x\) 在原始数组中出现过，对于 \(x\) 自身的操作，没有意义，因此会有 \(s - cnt[x]\) 个其他的元素可以通过操作变为 \(x\)，但最多只能操作 \(\textit{numOperations}\) 次，所以该位置的最大频率为 \(\textit{cnt}[x] + \min(s - \textit{cnt}[x], \textit{numOperations})\)。
- 如果 \(x\) 在原始数组中没有出现过，那么最多只能通过操作 \(\textit{numOperations}\) 次将其他元素变为 \(x\)，因此该位置的最大频率为 \(\min(s, \textit{numOperations})\)。
综合以上两种情况，我们可以统一表示为 \(\min(s, \textit{cnt}[x] + \textit{numOperations})\)。
最后，我们遍历所有位置，计算出每个位置的最大频率，并取其中的最大值作为答案。
时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为数组 \(\textit{nums}\) 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution {
public int maxFrequency(int[] nums, int k, int numOperations) {
Map<Integer, Integer> cnt = new HashMap<>();
TreeMap<Integer, Integer> d = new TreeMap<>();
for (int x : nums) {
cnt.merge(x, 1, Integer::sum);
d.putIfAbsent(x, 0);
d.merge(x - k, 1, Integer::sum);
d.merge(x + k + 1, -1, Integer::sum);
}
int ans = 0, s = 0;
for (var e : d.entrySet()) {
int x = e.getKey(), t = e.getValue();
s += t;
ans = Math.max(ans, Math.min(s, cnt.getOrDefault(x, 0) + numOperations));
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public:
int maxFrequency(vector<int>& nums, int k, int numOperations) {
unordered_map<int, int> cnt;
map<int, int> d;
for (int x : nums) {
cnt[x]++;
d[x];
d[x - k]++;
d[x + k + 1]--;
}
int ans = 0, s = 0;
for (const auto& [x, t] : d) {
s += t;
ans = max(ans, min(s, cnt[x] + numOperations));
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | func maxFrequency(nums []int, k int, numOperations int) (ans int) {
cnt := make(map[int]int)
d := make(map[int]int)
for _, x := range nums {
cnt[x]++
d[x] = d[x]
d[x-k]++
d[x+k+1]--
}
s := 0
keys := make([]int, 0, len(d))
for key := range d {
keys = append(keys, key)
}
sort.Ints(keys)
for _, x := range keys {
s += d[x]
ans = max(ans, min(s, cnt[x]+numOperations))
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | function maxFrequency(nums: number[], k: number, numOperations: number): number {
const cnt: Record<number, number> = {};
const d: Record<number, number> = {};
for (const x of nums) {
cnt[x] = (cnt[x] || 0) + 1;
d[x] = d[x] || 0;
d[x - k] = (d[x - k] || 0) + 1;
d[x + k + 1] = (d[x + k + 1] || 0) - 1;
}
let [ans, s] = [0, 0];
const keys = Object.keys(d)
.map(Number)
.sort((a, b) => a - b);
for (const x of keys) {
s += d[x];
ans = Math.max(ans, Math.min(s, (cnt[x] || 0) + numOperations));
}
return ans;
}
|