3346.执行操作后元素的最高频率 I：滑动窗口（正好适合本题数据，II再另谋他法）

【LetMeFly】3346.执行操作后元素的最高频率 I：滑动窗口（正好适合本题数据，II再另某他法）

力扣题目链接：https://leetcode.cn/problems/maximum-frequency-of-an-element-after-performing-operations-i/

给你一个整数数组 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 <= 105
• 1 <= nums[i] <= 105
• 0 <= k <= 105
• 0 <= numOperations <= nums.length

解题方法：滑动窗口

数组中元素顺序不影响结果，所以可以先对数组排个序。

统计每个数出现了多少次，然后从$nums$中最小值到最大值枚举$target$。对于一个$target$，计算将尽可能多的数变成$target$的话最终最多出现多少个$target$。

使用两个指针$l$和$r$，$l$指向数组中第一个可以变成$target$的元素，$r$指向第一个由于太大而不可以变成$target$的元素。

$target$变化时，如有需要则不断右移$l$和$r$指针直到严格满足指针定义为止。

好了，我们得到了$nums[l, l + 1, l + 2, \dots, r - 1]$的共$r-l$个元素都能通过一次操作变成$target$，而题目限制最多进行$numOperations$次操作，前面哈希表的作用这不就来了吗。

通过哈希表可以快速得知已有$already$个$target$，相当于有$already$个元素不需要操作。所以最终最多能有$\min(r-l, numOperations+already)$个元素变成$target$。

• 时间复杂度$O(len(nums)+\max(nums))$，而最高频率I和II的区别就在于$nums$的范围，本解法无法通过最高频率II。
• 空间复杂度$O(len(nums))$

AC代码

C++

/*
 * @LastEditTime: 2025-10-30 22:53:20
 */
class Solution {
public:
    int maxFrequency(vector<int>& nums, int k, int numOperations) {
        sort(nums.begin(), nums.end());
        unordered_map<int, int> frequency;
        for (int t : nums) {
            frequency[t]++;
        }
        int ans = 0;
        for (int l = 0, r = 0, target = nums[0]; target <= nums.back(); target++) {
            while (target - nums[l] > k) {
                l++;
            }
            while (r < nums.size() && nums[r] - target <= k) {
                r++;
            }
            ans = max(ans, min(r - l, numOperations + frequency[target]));
        }
        return ans;
    }
};

Python

'''
LastEditTime: 2025-10-30 22:57:07
'''
from typing import List
from collections import Counter

class Solution:
    def maxFrequency(self, nums: List[int], k: int, numOperations: int) -> int:
        nums.sort()
        frequency = Counter(nums)
        l = r = 0
        ans = 0
        for target in range(nums[0], nums[-1] + 1):
            while target - nums[l] > k:
                l += 1
            while r < len(nums) and nums[r] - target <= k:
                r += 1
            ans = max(ans, min(r - l, numOperations + frequency[target]))
        return ans  # 刚刚差点忘记return

Java

/*
 * @LastEditTime: 2025-10-30 23:07:34
 */
import java.util.Map;
import java.util.HashMap;
import java.util.Arrays;

class Solution {
    public int maxFrequency(int[] nums, int k, int numOperations) {
        Arrays.sort(nums);
        Map<Integer, Integer> frequency = new HashMap<>();
        for (int t : nums) {
            frequency.merge(t, 1, Integer::sum);  // 这个api挺容易忘的
        }
        int ans = 0, n = nums.length;
        for (int l = 0, r = 0, target = nums[0]; target <= nums[n - 1]; target++) {
            while (target - nums[l] > k) {
                l++;
            }
            while (r < n && nums[r] - target <= k) {
                r++;
            }
            ans = Math.max(ans, Math.min(r - l, numOperations + frequency.getOrDefault(target, 0)));
        }
        return ans;
    }
}

Go

/*
 * @LastEditTime: 2025-10-30 23:00:59
 */
package main

import "sort"

func maxFrequency(nums []int, k int, numOperations int) (ans int) {
    sort.Ints(nums)
    frequency := map[int]int{}
    for _, t := range nums {
        frequency[t]++
    }
    n := len(nums)
    for l, r, target := 0, 0, nums[0]; target <= nums[n - 1]; target++ {
        for target - nums[l] > k {
            l++
        }
        for r < n && nums[r] - target <= k {
            r++
        }
        ans = max(ans, min(r - l, numOperations + frequency[target]))
    }
    return
}

Rust

/*
 * @LastEditTime: 2025-10-30 23:19:32
 */
use std::collections::HashMap;
// 这台机器上没有安装过rust，故无IDE语法检查了
impl Solution {
    pub fn max_frequency(mut nums: Vec<i32>, k: i32, num_operations: i32) -> i32 {
        nums.sort();
        let mut frequency = HashMap::new();
        for &t in &nums {
            *frequency.entry(t).or_insert(0) += 1;  // 不存在时默认值为0
        }
        
        let mut ans: i32 = 0;
        let mut l: usize = 0;
        let mut r: usize = 0;
        for target in nums[0]..=nums[nums.len()-1] {
            while target - nums[l] > k {
                l += 1;
            }
            while r < nums.len() && nums[r] - target <= k {
                r += 1;
            }
            ans = ans.max(((r - l) as i32).min(num_operations + *frequency.get(&target).unwrap_or(&0)));
        }
        ans
    }
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源

今天发现github copilot可以根据review意见提pr了诶。