给你一个下标从 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 次,所以频率分数为 3 。
3 是所有可行方案里的最大频率分数。
class Solution:def maxFrequencyScore(self, nums: List[int], k: int) -> int:nums.sort()n = len(nums)pre = [n for n in nums]pre.insert(0, 0)for i in range(1, n + 1):pre[i] += pre[i - 1]def count(left, right):mid = (left + right) // 2return (pre[right + 1]- pre[mid + 1]- (right - mid) * nums[mid]+ nums[mid] * (mid - left)- (pre[mid] - pre[left]))left = 0res = 0for right in range(n):while count(left, right) > k:left += 1res = max(res, right - left + 1)return res