Leetcode1838. 最高频元素的频数

元素的频数"/>

Leetcode1838. 最高频元素的频数

Every day a Leetcode

题目来源：1838. 最高频元素的频数

解法1：排序 + 滑动窗口

发现1：操作后的最高频元素必定可以是数组中已有的某一个元素。

发现2：优先操作距离目标值最近的（小于目标值的）元素。

将数组 nums 排序，遍历排序后数组每个元素 nums[i] 作为目标值，并求出此时按贪心策略可以改变至目标值的元素左边界。

我们使用 left 与 right 作为执行操作的左右边界（闭区间），同时用 total 来维护将 [left, right] 区间全部变为末尾元素的操作次数。

在顺序枚举目标值（右边界）的同时，我们更新对应的左边界，并用 max_frq 来维护满足限制的最大区间元素数量即可。

更新对应的左边界的同时， total也要更新：

total -= diff

代码：

/** @lc app=leetcode id=1838 lang=cpp** [1838] 最高频元素的频数*/// @lc code=start
class Solution
{
public:int maxFrequency(vector<int> &nums, int k){int n = nums.size();sort(nums.begin(), nums.end());int left = 0;int max_frq = 1;long long sum = 0;// 枚举窗口的右边界for (int right = 1; right < n; right++){long long addition = 1LL * (nums[right] - nums[right - 1]) * (right - left);sum += addition;// 修改窗口的左边界while (sum > k){int diff = nums[right] - nums[left];sum -= diff;left++;}int cur_frq = right - left + 1;max_frq = max(max_frq, cur_frq);}return max_frq;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。

空间复杂度：O(1).

解法2：前缀和 + 二分

题解：【1838. 最高频元素的频数】C++解法:「前缀和+二分」