Medium

题目描述

元素的频数是指该元素在数组中出现的次数。

给你一个整数数组 nums 和一个整数 k。在一次操作中，你可以选择 nums 的一个下标，并将该下标对应元素的值增加 1。

返回在最多 k 次操作后，数组中最高频元素的最大可能频数。

示例 1：

输入：nums = [1,2,4], k = 5
输出：3
解释：对第一个元素使用 3 次操作，对第二个元素使用 2 次操作，使 nums = [4,4,4]。
4 的频数为 3。

示例 2：

输入：nums = [1,4,8,13], k = 5
输出：2
解释：存在多种最优解决方案：
- 对第一个元素使用 3 次操作，使 nums = [4,4,8,13]。4 的频数为 2。
- 对第二个元素使用 4 次操作，使 nums = [1,8,8,13]。8 的频数为 2。
- 对第三个元素使用 5 次操作，使 nums = [1,4,13,13]。13 的频数为 2。

示例 3：

输入：nums = [3,9,6], k = 2
输出：1

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5
  • 1 <= k <= 10^5

解题思路

这道题要求在最多进行 k 次加 1 操作后，找出数组中某个元素的最大可能频数。关键insight是：要让某个值的频数最大，我们应该将其他较小的值都增加到这个值。

解题思路有两种主要方法：

方法一：滑动窗口（推荐）

  1. 首先对数组排序，这样便于处理连续的元素区间
  2. 使用滑动窗口技巧，窗口内的所有元素都增加到窗口右端点的值
  3. 对于窗口 [left, right]，需要的操作次数为：nums[right] * (right - left + 1) - sum(nums[left:right+1])
  4. 当操作次数超过 k 时，收缩左边界；否则扩展右边界并更新最大频数

方法二：枚举目标值 + 贪心 枚举每个可能的目标值，对于每个目标值，贪心地选择最大的不超过该值的元素进行增加操作。

滑动窗口方法时间复杂度更优，是首选解法。核心在于维护一个有效的窗口，使得窗口内所有元素都能在 k 次操作内变成窗口右端点的值。

代码实现

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        long long sum = 0;
        int left = 0, maxFreq = 1;
        
        for (int right = 0; right < n; right++) {
            sum += nums[right];
            
            while ((long long)nums[right] * (right - left + 1) - sum > k) {
                sum -= nums[left];
                left++;
            }
            
            maxFreq = max(maxFreq, right - left + 1);
        }
        
        return maxFreq;
    }
};

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)
        total = 0
        left = 0
        max_freq = 1
        
        for right in range(n):
            total += nums[right]
            
            while nums[right] * (right - left + 1) - total > k:
                total -= nums[left]
                left += 1
            
            max_freq = max(max_freq, right - left + 1)
        
        return max_freq

public class Solution {
    public int MaxFrequency(int[] nums, int k) {
        Array.Sort(nums);
        int n = nums.Length;
        long sum = 0;
        int left = 0, maxFreq = 1;
        
        for (int right = 0; right < n; right++) {
            sum += nums[right];
            
            while ((long)nums[right] * (right - left + 1) - sum > k) {
                sum -= nums[left];
                left++;
            }
            
            maxFreq = Math.Max(maxFreq, right - left + 1);
        }
        
        return maxFreq;
    }
}

var maxFrequency = function(nums, k) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let sum = 0;
    let left = 0, maxFreq = 1;
    
    for (let right = 0; right < n; right++) {
        sum += nums[right];
        
        while (nums[right] * (right - left + 1) - sum > k) {
            sum -= nums[left];
            left++;
        }
        
        maxFreq = Math.max(maxFreq, right - left + 1);
    }
    
    return maxFreq;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型滑动窗口解法
时间复杂度O(n log n)
空间复杂度O(1)

说明：

  • 时间复杂度：O(n log n) 主要来自排序，滑动窗口部分是 O(n)
  • 空间复杂度：O(1) 只使用了常数额外空间（不计算排序的空间）

相关题目