[Python手撕]执行操作使频率分数最大
给你一个下标从 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) // 2
return (
pre[right + 1]
- pre[mid + 1]
- (right - mid) * nums[mid]
+ nums[mid] * (mid - left)
- (pre[mid] - pre[left])
)
left = 0
res = 0
for right in range(n):
while count(left, right) > k:
left += 1
res = max(res, right - left + 1)
return res