题目描述

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

你必须对 nums 执行 操作 numOperations 次。每次操作中，你可以：

• 选择一个下标 i，它在之前的操作中 没有 被选择过。
• 将 nums[i] 增加范围 [-k, k] 中的一个整数。

在执行完所有操作以后，请你返回 nums 中出现 频率最高 元素的出现次数。

一个元素 x 的 频率 指的是它在数组中出现的次数。

样例

输入：nums = [1,4,5], k = 1, numOperations = 2

输出：2

解释：

通过以下操作得到最高频率 2：

将 nums[1] 增加 0，nums 变为 [1, 4, 5]。
将 nums[2] 增加 -1，nums 变为 [1, 4, 4]。

输入：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

算法

(排序，双指针) $O(n \log n + U + k)$

1. 将数组按照顺序从小到大排序。
2. 从小到大枚举每一个可能的最终出现次数最多的数字，从最小值减 $k$，到最大值加 $k$。
3. 枚举过程中，维护两套双指针，第一套双指针维护距离当前数字范围在 $[-k, k]$ 的下标范围。第二套双指针维护值等于当前数字的下标范围。
4. 第一套双指针的范围减去第二套双指针的范围就是将结果修改为当前数字所需要的最少操作次数，如果这个操作次数小于等于 $numOperations$，则可以用第一套双指针的范围更新答案。
5. 否则，需要用第二套双指针的范围加上 $numOperations$ 来更新答案。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$。
• 排序后，枚举的范围为 $O(U + k)$。其中 $U$ 为最大可能的数字。
• 双指针总共需要的时间为 $O(n)$。
• 故总时间复杂度为 $O(n \log n + U + k)$。

空间复杂度

• 需要 $O(\log n)$ 的额外空间存储排序的系统栈。

C++ 代码

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k, int numOperations) {
        const int n = nums.size();

        sort(nums.begin(), nums.end());

        int l = 0, r = 0, le = 0, re = 0;
        int ans = 0;

        for (int x = nums[0] - k; x <= nums.back() + k; x++) {
            while (l < n && nums[l] + k < x) ++l;
            while (r < n && x + k >= nums[r]) ++r;

            while (le < n && nums[le] < x) ++le;
            while (re < n && x >= nums[re]) ++re;

            if (r - l - (re - le) <= numOperations)
                ans = max(ans, r - l);
            else
                ans = max(ans, numOperations + (re - le));
        }

        return ans;
    }
};