type
status
date
slug
summary
tags
category
icon
password
创建时间
Apr 13, 2025 02:13 AM
给你一个下标从 0 开始的整数数组
nums 和一个整数 k 。你可以对数组执行 至多
k 次操作：- 从数组中选择一个下标
i，将nums[i]增加 或者 减少1。
最终数组的频率分数定义为数组中众数的 频率 。
请你返回你可以得到的 最大 频率分数。
众数指的是数组中出现次数最多的数。一个元素的频率指的是数组中这个元素的出现次数。
不定长滑动窗口 + 前缀和
在写本题的时候，可以先看 2602. 使数组元素全部相等的最少操作次数 这道题。
但是，这道题我在思考的时候，想不到左窗口移动的判断条件。
参考 灵茶山艾府
需要知道中位数贪心：
定理：将
nums 的所有元素变为 nums 的中位数是最优的。为方便描述，将
nums 简记为 a。证明：设 a 的长度为 n，设要将所有 a[i] 变为 x。假设 a 已经从小到大排序。首先，如果 x 取在区间 [a[0],a[n−1]] 之外，那么 x 向区间方向移动可以使距离和变小；同时，如果 x 取在区间 [a[0],a[n−1]] 之内，无论如何移动 x，它到 a[0] 和 a[n−1] 的距离和都是一个定值 a[n−1]−a[0]，那么去掉 a[0] 和 a[n−1] 这两个最左最右的数，问题规模缩小。不断缩小问题规模，如果最后剩下 1 个数，那么 x 就取它；如果最后剩下 2 个数，那么 x 取这两个数之间的任意值都可以（包括这两个数）。因此 x 可以取 a[n/2]。