文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

元素的 頻數 是該元素在一個數組中出現的次數。

給你一個整數數組 nums 和一個整數 k 。
在一步操作中，你可以選擇 nums 的一個下標，并將該下標對應元素的值增加 1 。

執行最多 k 次操作后，返回數組中最高頻元素的 最大可能頻數 。

示例 1： 輸入：nums = [1,2,4], k = 5 輸出：3 解釋：對第一個元素執行 3 次遞增操作，對第二個元素執 2 次遞增操作， 此時 nums = [4,4,4] 。 4 是數組中最高頻元素，頻數是 3 。示例 2： 輸入：nums = [1,4,8,13], k = 5 輸出：2 解釋：存在多種最優解決方案： - 對第一個元素執行 3 次遞增操作，此時 nums = [4,4,8,13] 。 4 是數組中最高頻元素，頻數是 2 。 - 對第二個元素執行 4 次遞增操作，此時 nums = [1,8,8,13] 。 8 是數組中最高頻元素，頻數是 2 。 - 對第三個元素執行 5 次遞增操作，此時 nums = [1,4,13,13] 。 13 是數組中最高頻元素，頻數是 2 。示例 3： 輸入：nums = [3,9,6], k = 2 輸出：1提示： 1 <= nums.length <= 10^5 1 <= nums[i] <= 10^5 1 <= k <= 10^5

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/frequency-of-the-most-frequent-element
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 對數字進行排序（只有小的數能通過操作變成大的數），并求前綴和
• 二分求解最大頻次
• 每次二分的時候，遍歷一次前綴和數組，以某位置為最大頻數的數字，能不能滿足要求？根據結果，調整區間

類似題目：
LeetCode 1231. 分享巧克力（極小極大化 二分查找）

class Solution {int ans = 1; public:int maxFrequency(vector<int>& nums, int k) {sort(nums.begin(), nums.end());vector<long> presum(nums.size()+1);for(int i = 1; i <= nums.size(); ++i)presum[i] = presum[i-1]+nums[i-1];int l = 1, r = 1e5, mid;while(l <= r){mid = l+((r-l)>>1);if(ok(nums, presum, mid, k))//在最大頻數為mid的時候，能做到嗎？{ans = mid;//能l = mid+1;}elser = mid-1;}return ans;}bool ok(vector<int>& nums, vector<long>& presum, long freq, int k){for(int i = freq; i < presum.size(); i++){if(presum[i]-presum[i-freq]+k >= nums[i-1]*freq)// 包含 i 位置在內的前面 freq 個數字都變成 i 位置處的數字，能做到嗎return true;}return false;} };

272 ms 84 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1838. 最高频元素的频数（二分查找）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。