1838. Frequency of the Most Frequent Element

周賽複盤

這題很巧妙, 可以再每個加值(但有上限), 然後求相同出現頻率最多的Case

舉例

[1, 2, 4]
k = 5

我們可以將 1 加到4, 2 加到4, 然後就變成

[4, 4, 4]
其中我們只加了3, 所以小於 k(5), 這邊頻率次數出現最多就是4一共出現3次

這邊我開始的想法方向錯了

我們先sort, 然後用sliding windows, 用一個sum存每次走過的值,在遍歷每個值的時候, 我們會把當前走到的值當成我們要設定的頻率數字, 然後直接看他到left跟sum的差距是多少, 如果已經超過k的情況, 我們就把left往後移一個, 直到符合規定

因為sum很可能會超出int的size, 要用long

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        long sum = 0;
        long left = 0;
        long res = 0;
        for(int i = 0; i < nums.size();i++){
            sum += nums[i];
            while((i - left + 1) * nums[i] - sum > k){
                sum -=nums[left];
                left++;
            }
            res = max(res, i - left + 1);
        }
        return res;
    }
};