Leetcode 1838. 最高频元素的频数（DAY 132) ---- 贪心算法学习期

﹏ヽ暗。殇╰゛Y 2022-10-05 04:43 113阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷看了点思路）
     *  代码实现（二刷自解 DAY 185 C++）

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70]

--------------------

## 代码实现（首刷看了点思路） ##

--------------------

class Solution { 
    public:
        int maxFrequency(vector<int>& nums, int k) { 
            long tempsum = 0;
            int ret = 0;
            sort(nums.begin(),nums.end());
            for(int l=0,r=0;l<nums.size();++l)
            { 
                while(r<nums.size()-1 && tempsum <= k)
                { 
                    tempsum += (long long)(nums[r+1] - nums[r])*(r-l+1);
                    ++r;
                }
                if(tempsum <= k)    ret = max(ret,r-l+1);
                else    ret = max(ret,r-l);
                tempsum -= (nums[r] - nums[l]);
            }
            return ret;
        }
    };

--------------------

## 代码实现（二刷自解 DAY 185 C++） ##

--------------------

class Solution { 
    public:
        int maxFrequency(vector<int>& nums, int k) { 
            sort(nums.begin(),nums.end());
            int left = 0,right = 0,maxnum = nums[left],ret = 0;
            while(right != nums.size())
            { 
                while(k >= 0 && right != nums.size())
                { 
                    long tmp = static_cast<long>((nums[right] - maxnum)) * (right - left);
                    maxnum = nums[right++];
                    k -= tmp;
                    if(k >= 0)  ret = max(right - left,ret);
                }
                
                while(k < 0)
                    k += (maxnum - nums[left++]);
            }   
            return ret;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70]: /images/20221005/b8e880d478e14d24b3166ca08a6125b4.png