class Solution {
public:
int maxFrequency(vector<int>& nums, int k, int numOperations) {
}
};
3347. 执行操作后元素的最高频率 II
给你一个整数数组 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] <= 1090 <= k <= 1090 <= numOperations <= nums.length原站题解
golang 解法, 执行用时: 447 ms, 内存消耗: 41.4 MB, 提交时间: 2024-11-18 22:47:26
func maxFrequency(nums []int, k, numOperations int) (ans int) {
cnt := map[int]int{}
diff := map[int]int{}
for _, x := range nums {
cnt[x]++
diff[x] += 0 // 把 x 插入 diff，以保证下面能遍历到 x
diff[x-k]++ // 把 [x-k, x+k] 中的每个整数的出现次数都加一
diff[x+k+1]--
}
sumD := 0
for _, x := range slices.Sorted(maps.Keys(diff)) {
sumD += diff[x]
ans = max(ans, min(sumD, cnt[x]+numOperations))
}
return
}
java 解法, 执行用时: 32 ms, 内存消耗: 55.3 MB, 提交时间: 2024-11-18 22:46:52
class Solution {
public int maxFrequency(int[] nums, int k, int numOperations) {
Arrays.sort(nums);
int n = nums.length;
int ans = 0;
int cnt = 0;
int left = 0;
int right = 0;
int left2 = 0;
for (int i = 0; i < n; i++) {
int x = nums[i];
while (nums[left2] < x - k * 2) {
left2++;
}
ans = Math.max(ans, Math.min(i - left2 + 1, numOperations));
cnt++;
// 循环直到连续相同段的末尾，这样可以统计出 x 的出现次数
if (i < n - 1 && x == nums[i + 1]) {
continue;
}
while (nums[left] < x - k) {
left++;
}
while (right < n && nums[right] <= x + k) {
right++;
}
ans = Math.max(ans, Math.min(right - left, cnt + numOperations));
cnt = 0;
}
return ans;
}
}
python3 解法, 执行用时: 1546 ms, 内存消耗: 76.2 MB, 提交时间: 2024-11-18 22:46:32
class Solution:
# 差分
def maxFrequency(self, nums: List[int], k: int, numOperations: int) -> int:
cnt = defaultdict(int)
diff = defaultdict(int)
for x in nums:
cnt[x] += 1
diff[x] # 把 x 插入 diff，以保证下面能遍历到 x
diff[x - k] += 1 # 把 [x-k,x+k] 中的每个整数的出现次数都加一
diff[x + k + 1] -= 1
ans = sum_d = 0
for x, d in sorted(diff.items()):
sum_d += d
ans = max(ans, min(sum_d, cnt[x] + numOperations))
return ans