Medium

题目描述

给你一个整数数组 nums 和两个整数 k 和 numOperations。

你必须对 nums 执行 numOperations 次操作，其中每次操作你需要：

  • 选择一个在之前操作中未被选择过的下标 i。
  • 给 nums[i] 加上一个范围在 [-k, k] 内的整数。

返回执行操作后 nums 中任意元素可能的最大频率。

示例 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

解题思路

这道题的核心思想是枚举所有可能的目标值，然后计算对于每个目标值，最多能有多少个元素可以通过操作变成该值。

解题思路：

  1. 排序：首先对数组排序，便于后续处理。

  2. 枚举目标值：对于每个可能的目标值 target，我们需要：

    • 统计原数组中已经等于 target 的元素个数（这些不需要操作）
    • 统计可以通过操作变成 target 的元素个数

  3. 滑动窗口：对于目标值 target，一个元素 nums[i] 可以变成 target 当且仅当 |nums[i] - target| <= k，即 target - k <= nums[i] <= target + k。由于数组已排序，我们可以用滑动窗口快速找到这个范围内的所有元素。

  4. 贪心选择：在可操作的元素中，优先选择那些已经等于目标值的元素（无需操作），然后选择需要操作的元素，直到操作次数用完。

优化点：

  • 我们只需要考虑数组中存在的值以及它们附近的值作为目标值
  • 使用二分查找可以快速定位滑动窗口的边界

时间复杂度主要来自排序和对每个可能目标值的处理。

代码实现

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k, int numOperations) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int maxFreq = 0;
        
        // 收集所有可能的目标值
        set<int> targets;
        for (int num : nums) {
            targets.insert(num);
            targets.insert(num - k);
            targets.insert(num + k);
        }
        
        for (int target : targets) {
            // 计算原本就等于target的元素个数
            int originalCount = 0;
            for (int num : nums) {
                if (num == target) originalCount++;
            }
            
            // 使用二分查找找到可以变成target的元素范围
            int left = lower_bound(nums.begin(), nums.end(), target - k) - nums.begin();
            int right = upper_bound(nums.begin(), nums.end(), target + k) - nums.begin() - 1;
            
            if (left <= right) {
                int canTransform = right - left + 1;
                int needOperations = canTransform - originalCount;
                
                // 最多可以使用的操作次数
                int usableOps = min(needOperations, numOperations);
                int totalFreq = originalCount + usableOps;
                
                maxFreq = max(maxFreq, totalFreq);
            }
        }
        
        return maxFreq;
    }
};

class Solution:
    def maxFrequency(self, nums: List[int], k: int, numOperations: int) -> int:
        nums.sort()
        n = len(nums)
        max_freq = 0
        
        # 收集所有可能的目标值
        targets = set()
        for num in nums:
            targets.add(num)
            targets.add(num - k)
            targets.add(num + k)
        
        for target in targets:
            # 计算原本就等于target的元素个数
            original_count = nums.count(target)
            
            # 使用二分查找找到可以变成target的元素范围
            left = bisect.bisect_left(nums, target - k)
            right = bisect.bisect_right(nums, target + k) - 1
            
            if left <= right:
                can_transform = right - left + 1
                need_operations = can_transform - original_count
                
                # 最多可以使用的操作次数
                usable_ops = min(need_operations, numOperations)
                total_freq = original_count + usable_ops
                
                max_freq = max(max_freq, total_freq)
        
        return max_freq

public class Solution {
    public int MaxFrequency(int[] nums, int k, int numOperations) {
        Array.Sort(nums);
        int n = nums.Length;
        int maxFreq = 0;
        
        // 收集所有可能的目标值
        var targets = new HashSet<int>();
        foreach (int num in nums) {
            targets.Add(num);
            targets.Add(num - k);
            targets.Add(num + k);
        }
        
        foreach (int target in targets) {
            // 计算原本就等于target的元素个数
            int originalCount = 0;
            foreach (int num in nums) {
                if (num == target) originalCount++;
            }
            
            // 使用二分查找找到可以变成target的元素范围
            int left = Array.BinarySearch(nums, target - k);
            if (left < 0) left = ~left;
            
            int right = Array.BinarySearch(nums, target + k);
            if (right < 0) right = ~right - 1;
            else {
                // 找到最后一个等于target + k的位置
                while (right < n - 1 && nums[right + 1] == target + k) {
                    right++;
                }
            }
            
            if (left <= right) {
                int canTransform = right - left + 1;
                int needOperations = canTransform - originalCount;
                
                // 最多可以使用的操作次数
                int usableOps = Math.Min(needOperations, numOperations);
                int totalFreq = originalCount + usableOps;
                
                maxFreq = Math.Max(maxFreq, totalFreq);
            }
        }
        
        return maxFreq;
    }
}

var maxFrequency = function(nums, k, numOperations) {
    const n = nums.length;
    const freq = new Map();
    
    // Count original frequencies
    for (const num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }
    
    // Get all possible target values
    const targets = new Set();
    for (const num of nums) {
        targets.add(num);
        for (let i = num - k; i <= num + k; i++) {
            targets.add(i);
        }
    }
    
    let maxFreq = 0;
    
    for (const target of targets) {
        let unchanged = freq.get(target) || 0;
        let canChange = 0;
        
        for (const num of nums) {
            if (num !== target && Math.abs(num - target) <= k) {
                canChange++;
            }
        }
        
        const operations = Math.min(canChange, numOperations);
        maxFreq = Math.max(maxFreq, unchanged + operations);
    }
    
    return maxFreq;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n² log n)，其中 n 是数组长度。排序需要 O(n log n)，枚举目标值最多 3n 个，每个目标值的处理需要 O(n log n)（二分查找）
空间复杂度O(n)，用于存储目标值集合

相关题目