题目
给你一个下标从 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 是所有可行方案里的最大频率分数。
示例 2：
输入：nums = [1,4,4,2,4], k = 0
输出：3
解释：我们无法执行任何操作，所以得到的频率分数是原数组中众数的频率 3 。
参数范围：
1 <= nums.length <= 105
1 <= nums[i] <= 109
0 <= k <= 1014
贪心算法（中位数贪心)
假定众数是x,假定nums的长度为n，将nums按升序排序。
x一定是nums中的数
我们用反证发证明。
| x < nums[0] | 所有数先降到nums[0]，再由nums[0]降到x，不如直接降到nums[0] |
| x > nums[n-1] | 所有数先升到nums[n-1]，再升到x，不如只升到nums[n-1] |
| x在nums[i]和nums[j]之间，nums中比x小的a个数，比x大的b个数。 | 如果a>=b，x–,可以节省a-b个操作，直到x等于nums[i];否则x++，直到x等于nums[j]。 |
改变的数一定是一个子数组
假定改变的数是两个子数组[i1,i2]和[i3,i4]。如果x在[i1,i2]之间，则将i4替换成i2+1，直到两个子数组挨着一起合并。如果x在[i3,i4]之间，则i1替换i3-1，直到两个子数组挨着一起合并。
x只需要考虑中位数（中位数贪心算法)
来证明贪心算法的正确性。假定x是nums[i]，x前面的数a个，x后面的数b个，i变成i-1操作次数变化：b-(a-1)，如果表达式大于等于0，则没必要左移。b -a+1 >= 0，即a <=b+1。同理b <=a+1。即abs(a-b)<=1，则没必要左移和右移。
即：
如果n为偶数，中间任意一个。
如果n为奇数，中间的那个。
代码
核心代码
class Solution { public: int maxFrequencyScore(vector<int>& nums, long long k) { m_c = nums.size(); sort(nums.begin(), nums.end()); vector<long long> vPreSum = { 0 }; for (const auto& n : nums) { vPreSum.emplace_back(n+vPreSum.back()); } int iRet = 0; for (int left = 0, right = 0; left < m_c; left++) { while (right <= m_c) { const long long mid = left + (right - left) / 2; const long long llLessNeed = (mid - left) * nums[mid] - (vPreSum[mid] - vPreSum[left]); const long long llEqualMoreNeed = (vPreSum[right] - vPreSum[mid]) - nums[mid] * (right - mid); if (llLessNeed + llEqualMoreNeed <= k) { iRet = max(iRet, right - left); right++; } else { break; } } } return iRet; } int m_c; };
测试用例
void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { Solution slu; vector<int> nums; int k; { Solution slu; nums = { 1,4,4,2,4 }, k = 0; auto res = slu.maxFrequencyScore(nums, k); Assert(3, res); } { Solution slu; nums = { 16, 2, 6, 20, 2, 18, 16, 8, 15, 19, 22, 29, 24, 2, 26, 19 }, k = 40; auto res = slu.maxFrequencyScore(nums, k); Assert(11, res); } { Solution slu; nums = { 1, 2, 6, 4 }, k = 3; auto res = slu.maxFrequencyScore(nums, k); Assert(3, res); } //CConsole::Out(res); }
错误解法:二分查找+双指针
错误原因： 随着left增加targge可能减少
class Solution { public: int maxFrequencyScore(vector& nums, long long k) { m_c = nums.size(); sort(nums.begin(), nums.end()); vector vPreSum = { 0 }; for (const auto& n : nums) { vPreSum.emplace_back(n+vPreSum.back()); } long long llLeftSum = 0;//nums[left,target)的和，nums升序 int iRet = 0; for (int left = 0, target = 0; left < m_c; left++) { while ((target < m_c) && (nums[target]*(target-left)- llLeftSum <= k)) { const int right = BF(vPreSum,nums, target, k - (nums[target] * (target - left) - llLeftSum)); iRet = max(iRet, right - left); llLeftSum += nums[target]; target++; } llLeftSum -= nums[left]; } return iRet; } int BF(const vector& vPreSum,const vector& nums, int index,long long canUse) { int left = index, right = vPreSum.size(); while (right - left > 1) { const int mid = left + (right- left)/2 ; if ((vPreSum[mid] - vPreSum[index]- nums[index] * (mid - index)) <= canUse) { left = mid; } else { right = mid; } } return left; } int m_c; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
