题目描述

给你一个整数数组 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^9
• 0 <= k <= 10^9
• 0 <= numOperations <= nums.length

算法

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

1. 参考 执行操作后元素的最高频率 I 的做法。
2. 候选答案的范围可以缩减为每个数字 $nums(i)$ 的 $nums(i) - k, nums(i), nums(i) + k$。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$。
• 排序后，枚举的范围为 $O(n)$。
• 双指针总共需要的时间为 $O(n)$。
• 故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储排序的系统栈和目标候选数字数组。

C++ 代码

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

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

        vector<int> c;
        for (int x : nums) {
            c.push_back(x - k);
            c.push_back(x);
            c.push_back(x + k);
        }

        sort(c.begin(), c.end());
        c.resize(unique(c.begin(), c.end()) - c.begin());

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

        for (int x : c) {
            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;
    }
};