Hard

题目描述

给你一个整数数组 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
解释：
我们可以通过向 nums[1] 添加 0 来获得最大频率 2。

约束条件：

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

提示：

  • 需要检查的最优值是 nums[i] - k、nums[i] 和 nums[i] + k。

解题思路

这道题的核心思路是找到最优的目标值，使得通过有限次操作能够得到最大频率。

关键观察：

  1. 对于任意目标值 target，每个 nums[i] 只有在 target - k <= nums[i] <= target + k 时才能通过一次操作变为 target
  2. 根据提示，我们只需要考虑候选目标值：nums[i] - k、nums[i] 和 nums[i] + k

解法思路：

  1. 生成候选目标值：遍历所有 nums[i]，生成所有可能的目标值并去重排序
  2. 对每个目标值计算最大频率：
    • 统计原数组中已经等于目标值的元素数量（无需操作）
    • 统计可以通过一次操作变为目标值的元素数量（需要操作）
    • 在操作次数限制下，优先保留原有元素，剩余操作用于转换其他元素
  3. 优化计算：使用二分查找快速统计区间内的元素数量

时间复杂度分析：

  • 生成候选值：O(n)
  • 排序：O(n log n)
  • 对每个候选值计算：O(log n)（二分查找）
  • 总体：O(n log n)

这个解法比暴力枚举所有可能值要高效得多，利用了问题的特殊性质。

代码实现

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k, int numOperations) {
        sort(nums.begin(), nums.end());
        
        // 生成所有候选目标值
        set<long long> candidateSet;
        for (int num : nums) {
            candidateSet.insert((long long)num - k);
            candidateSet.insert(num);
            candidateSet.insert((long long)num + k);
        }
        
        vector<long long> candidates(candidateSet.begin(), candidateSet.end());
        int maxFreq = 0;
        
        for (long long target : candidates) {
            // 计算原本就等于target的元素数量
            int originalCount = upper_bound(nums.begin(), nums.end(), target) - 
                               lower_bound(nums.begin(), nums.end(), target);
            
            // 计算可以通过操作变为target的元素数量
            int convertibleCount = upper_bound(nums.begin(), nums.end(), target + k) - 
                                 lower_bound(nums.begin(), nums.end(), target - k);
            
            // 可以进行操作的元素数量
            convertibleCount -= originalCount;
            
            // 最大频率 = 原有数量 + min(可转换数量, 操作次数)
            int freq = originalCount + min(convertibleCount, numOperations);
            maxFreq = max(maxFreq, freq);
        }
        
        return maxFreq;
    }
};

class Solution:
    def maxFrequency(self, nums: List[int], k: int, numOperations: int) -> int:
        nums.sort()
        
        # 生成所有候选目标值
        candidates = set()
        for num in nums:
            candidates.add(num - k)
            candidates.add(num)
            candidates.add(num + k)
        
        candidates = sorted(candidates)
        max_freq = 0
        
        for target in candidates:
            # 使用二分查找计算原本就等于target的元素数量
            left = self.lower_bound(nums, target)
            right = self.upper_bound(nums, target)
            original_count = right - left
            
            # 计算可以通过操作变为target的元素数量
            conv_left = self.lower_bound(nums, target - k)
            conv_right = self.upper_bound(nums, target + k)
            convertible_count = conv_right - conv_left - original_count
            
            # 最大频率 = 原有数量 + min(可转换数量, 操作次数)
            freq = original_count + min(convertible_count, numOperations)
            max_freq = max(max_freq, freq)
        
        return max_freq
    
    def lower_bound(self, nums, target):
        left, right = 0, len(nums)
        while left < right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left
    
    def upper_bound(self, nums, target):
        left, right = 0, len(nums)
        while left < right:
            mid = (left + right) // 2
            if nums[mid] <= target:
                left = mid + 1
            else:
                right = mid
        return left

public class Solution {
    public int MaxFrequency(int[] nums, int k, int numOperations) {
        Array.Sort(nums);
        
        // 生成所有候选目标值
        var candidateSet = new HashSet<long>();
        foreach (int num in nums) {
            candidateSet.Add((long)num - k);
            candidateSet.Add(num);
            candidateSet.Add((long)num + k);
        }
        
        var candidates = candidateSet.ToList();
        candidates.Sort();
        int maxFreq = 0;
        
        foreach (long target in candidates) {
            // 计算原本就等于target的元素数量
            int originalCount = UpperBound(nums, target) - LowerBound(nums, target);
            
            // 计算可以通过操作变为target的元素数量
            int convertibleCount = UpperBound(nums, target + k) - LowerBound(nums, target - k);
            convertibleCount -= originalCount;
            
            // 最大频率 = 原有数量 + min(可转换数量, 操作次数)
            int freq = originalCount + Math.Min(convertibleCount, numOperations);
            maxFreq = Math.Max(maxFreq, freq);
        }
        
        return maxFreq;
    }
    
    private int LowerBound(int[] nums, long target) {
        int left = 0, right = nums.Length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    private int UpperBound(int[] nums, long target) {
        int left = 0, right = nums.Length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

var maxFrequency = function(nums, k, numOperations) {
    nums.sort((a, b) => a - b);
    
    // 生成所有候选目标值
    const candidateSet = new Set();
    for (let num of nums) {
        candidateSet.add(num - k);
        candidateSet.add(num);
        candidateSet.add(num + k);
    }
    
    const candidates = Array.from(candidateSet).sort((a, b) => a - b);
    let maxFreq = 0;
    
    const lowerBound = (nums, target) => {
        let left = 0, right = nums.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    };
    
    const upperBound = (nums, target) => {
        let left = 0, right = nums.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    };
    
    for (let target of candidates) {
        // 计算原本就等于target的元素数量
        const originalCount = upperBound(nums, target) - lowerBound(nums, target);
        
        // 计算可以通过操作变为target的元素数量
        let convertibleCount = upperBound(nums, target + k) - lowerBound(nums, target - k);
        convertibleCount -= originalCount;
        
        // 最大频率 = 原有数量 + min(可转换数量, 操作次数)
        const freq = originalCount + Math.min(convertibleCount, numOperations);
        maxFreq = Math.max(maxFreq, freq);
    }
    
    return maxFreq;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)排序 O(n log n) + 生成候选值 O(n) + 对每个候选值二分查找 O(n log n)
空间复杂度O(n)存储候选值集合，最多 3n 个不同值

相关题目