Hard

题目描述

给你一个下标从 0 开始的整数数组 nums 和一个整数 k。

你可以对数组执行以下操作最多 k 次：

  • 选择数组中的任意下标 i，将 nums[i] 增加或减少 1。

最终数组的分数是数组中出现最频繁元素的频次。

返回你能获得的最大分数。

元素的频次是该元素在数组中出现的次数。

示例 1：

输入：nums = [1,2,6,4], k = 3
输出：3
解释：我们可以对数组执行以下操作：
- 选择 i = 0，将 nums[0] 的值增加 1。结果数组是 [2,2,6,4]。
- 选择 i = 3，将 nums[3] 的值减少 1。结果数组是 [2,2,6,3]。
- 选择 i = 3，将 nums[3] 的值减少 1。结果数组是 [2,2,6,2]。
元素 2 是最终数组中出现最频繁的，所以我们的分数是 3。
可以证明我们无法获得更好的分数。

示例 2：

输入：nums = [1,4,4,2,4], k = 0
输出：3
解释：我们无法应用任何操作，所以我们的分数将是原数组中最频繁元素的频次，即 3。

约束：

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

解题思路

这是一个经典的二分查找 + 滑动窗口问题。

核心思路是：对于排序后的数组，最优策略是将某个连续子数组的所有元素变成相同的值。为什么？因为如果我们要让更多元素变成同一个值，选择连续的元素可以最小化总的操作次数。

具体解法分为以下步骤：

  1. 排序：首先对数组排序，这样相邻元素的差值最小，便于后续计算。

  2. 二分查找：对答案进行二分查找。答案的范围是 [1, n]，我们要找到最大的长度 len，使得存在某个长度为 len 的子数组可以在 k 次操作内变成相同值。

  3. 滑动窗口验证：对于给定的长度 len，使用滑动窗口检查是否存在长度为 len 的子数组满足条件。关键是选择目标值：对于子数组 [i, i+len-1]，最优的目标值是中位数 nums[(i+i+len-1)/2]，这样可以最小化总操作数。

  4. 操作数计算：对于子数组中的每个元素，计算其到目标值的距离，累加得到总操作数。如果总操作数不超过 k，则说明当前长度可行。

通过前缀和优化，我们可以在 O(1) 时间内计算子数组到目标值的总距离。

时间复杂度：排序 O(n log n) + 二分查找 O(log n) × 滑动窗口 O(n) = O(n log n)

代码实现

class Solution {
public:
    int maxFrequencyScore(vector<int>& nums, long long k) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        
        // 前缀和
        vector<long long> prefix(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        auto check = [&](int len) -> bool {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                int mid = (i + j) / 2;
                long long target = nums[mid];
                
                // 计算左半部分的操作数
                long long leftCost = (long long)(mid - i) * target - (prefix[mid] - prefix[i]);
                // 计算右半部分的操作数
                long long rightCost = (prefix[j + 1] - prefix[mid + 1]) - (long long)(j - mid) * target;
                
                if (leftCost + rightCost <= k) {
                    return true;
                }
            }
            return false;
        };
        
        int left = 1, right = n, ans = 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (check(mid)) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return ans;
    }
};

class Solution:
    def maxFrequencyScore(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums.sort()
        
        # 前缀和
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
        
        def check(length):
            for i in range(n - length + 1):
                j = i + length - 1
                mid = (i + j) // 2
                target = nums[mid]
                
                # 计算左半部分的操作数
                left_cost = (mid - i) * target - (prefix[mid] - prefix[i])
                # 计算右半部分的操作数
                right_cost = (prefix[j + 1] - prefix[mid + 1]) - (j - mid) * target
                
                if left_cost + right_cost <= k:
                    return True
            return False
        
        left, right, ans = 1, n, 1
        while left <= right:
            mid = (left + right) // 2
            if check(mid):
                ans = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return ans

public class Solution {
    public int MaxFrequencyScore(int[] nums, long k) {
        int n = nums.Length;
        Array.Sort(nums);
        
        // 前缀和
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        bool Check(int len) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                int mid = (i + j) / 2;
                long target = nums[mid];
                
                // 计算左半部分的操作数
                long leftCost = (long)(mid - i) * target - (prefix[mid] - prefix[i]);
                // 计算右半部分的操作数
                long rightCost = (prefix[j + 1] - prefix[mid + 1]) - (long)(j - mid) * target;
                
                if (leftCost + rightCost <= k) {
                    return true;
                }
            }
            return false;
        }
        
        int left = 1, right = n, ans = 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (Check(mid)) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return ans;
    }
}

var maxFrequencyScore = function(nums, k) {
    const n = nums.length;
    nums.sort((a, b) => a - b);
    
    // 前缀和
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    
    const check = (len) => {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;
            const mid = Math.floor((i + j) / 2);
            const target = nums[mid];
            
            // 计算左半部分的操作数
            const leftCost = (mid - i) * target - (prefix[mid] - prefix[i]);
            // 计算右半部分的操作数
            const rightCost = (prefix[j + 1] - prefix[mid + 1]) - (j - mid) * target;
            
            if (leftCost + rightCost <= k) {
                return true;
            }
        }
        return false;
    };
    
    let left = 1, right = n, ans = 1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (check(mid)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return ans;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n log n)
空间复杂度O(n)

其中 n 是数组长度。时间复杂度主要来自排序 O(n log n) 和二分查找过程中的滑动窗口验证 O(n log n)。空间复杂度来自前缀和数组的存储。

相关题目