3346. Maximum Frequency of an Element After Performing Operations I

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} numOperations
 * @return {number}
 */

本题给了一个数字数组 nums，要求我们在 numOperations 次操作内，求出数组中相同数字出现最高的频率是多少

一次操作指的是我们在 nums 中选择没有操作过的元素，将其元素与 [-k, k] 范围内的整数求和

解题思路

本题题目需要我们通过操作尽可能将 nums 中的数字变成一样的（让某个数字出现频率最高）

出现频率最高的数字有两种可能：

该数字是原来 nums 中的元素
该数字不是 nums 中的元素

下面我们分开讨论

目标是 nums 中的元素

这个情况下，我们就可以省去给该元素操作的次数，然后将这些次数用来操作别的元素

那么怎么操作呢？

首先我们需要对数组 nums 升序排序

然后我们需要遍历 nums 中的每一个元素

针对每一个元素，我们有两个指针：left、right

left 指针指向的元素是比当前 nums[i] - k 大的最小的元素，也就是：nums[left] >= nums[i] - k
right 指针指向的元素是比当前 nums[i] + k 大的最小元素，也就是：nums[right] > nums[i] + k

不难看出 right - left 就是当目标为 nums[i] 时，经过操作后能等于 nums[i] 的元素数量

但是题目还有一个操作限制，所以当目标是 nums[i] 时，出现的频率是：Math.min(right - left, numOperations + count)

其中 count 是 nums[i] 出现的次数

当我们把 nums 所有元素都遍历完了之后得到的最大值就是在目标是 nums 中的元素的情况下出现频率最高元素的出现次数了

目标不是nums 中的元素

在这种情况下，针对每一个 nums[i]，我们只需要看 [nums[i] - 2k, nums[i]] 这个范围内的元素个数就好

接下来我们把两种情况都处理完，得到的就是答案了

Javascript

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} numOperations
 * @return {number}
 */
var maxFrequency = function (nums, k, numOperations) {
    nums.sort((a, b) => a - b)
    const len = nums.length
    let res = 0

    // if nums[i] is target
    let left = 0
    let right = 0
    // count the current element
    let count = 0
    for (let i = 0; i < nums.length; i++) {
        count++
        if(i < len - 1 && nums[i+1] === nums[i]) {
            continue
        }
        // for each nums[i], calculate the left and right boundary
        // nums[left] >= nums[i] - k
        while(nums[left] < nums[i] - k) {
            left++
        }
        // nums[right] > nums[i] + k
        while(right < len && nums[right] <= nums[i] + k) {
            right++
        }
        // since nums[i] is target, we can keep the ops on nums[i] and its equivalent
        res = Math.max(res, Math.min(right - left, numOperations + count))
        count = 0
    }

    // if the answer is already exceed numOperations, we can just return
    if(res >= numOperations) {
        return res
    }

    // now, we can handle the situation that nums[i] is not a target
    left = 0
    const BOUNDARY = k*2
    for(right = 0;right < len;right++) {
        // we maintain a range of [(nums[right] - 2*k), (nums[right])]
        while(nums[right] - nums[left] > BOUNDARY) {
            left++
        }
        const size = right - left + 1
        res = Math.max(res, Math.min(numOperations, size))
    }

    return res
};

3346. Maximum Frequency of an Element After Performing Operations I(medium)