目标
给你一个整数数组 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
思路
对数组 nums 执行 numOperations 次操作，每次操作可以选一个没有被操作过的元素，将其增加 [-k, k] 之间的整数，求元素值的最大出现次数。
对数组排序，并针对元素进行计数，枚举值域范围内的每一个值，二分查找左右 k 范围内的元素个数。
代码
/**
* @date 2025-10-21 8:53
*/
public class MaxFrequency3346 {
public int maxFrequency(int[] nums, int k, int numOperations) {
int max = Arrays.stream(nums).max().getAsInt();
int[] cnt = new int[max + 1];
for (int num : nums) {
cnt[num]++;
}
Arrays.sort(nums);
int res = 1;
for (int i = 1; i <= max; i++) {
int l = lowerBound(nums, i - k);
int r = upperBound(nums, i + k);
res = Math.max(res, cnt[i] + Math.min(r - l + 1 - cnt[i], numOperations));
}
return res;
}
public int lowerBound(int[] nums, int target) {
int r = nums.length - 1;
int l = 0;
int mid = l + (r - l) / 2;
while (l <= r) {
if (nums[mid] >= target) {
r = mid - 1;
} else {
l = mid + 1;
}
mid = l + (r - l) / 2;
}
return l;
}
public int upperBound(int[] nums, int target) {
int r = nums.length - 1;
int l = 0;
int mid = l + (r - l) / 2;
while (l <= r) {
if (nums[mid] <= target) {
l = mid + 1;
} else {
r = mid - 1;
}
mid = l + (r - l) / 2;
}
return r;
}
}
性能
