3347. Maximum Frequency of an Element After Performing Operations II

Leetcode link

题目简介

这题跟 3346 的唯一区别就是 nums[i] 跟 k 的范围更大了，所以对算法复杂度的要求会更高，但是解法直接用 3346 的就行

解题思路

见 3346

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
};