class Solution {
public:
int maxFrequency(vector<int>& nums, int k) {
}
};
1838. 最高频元素的频数
元素的 频数 是该元素在一个数组中出现的次数。
给你一个整数数组 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 <= 1051 <= nums[i] <= 1051 <= k <= 105原站题解
cpp 解法, 执行用时: 192 ms, 内存消耗: 97 MB, 提交时间: 2023-09-24 22:56:24
class Solution {
public:
int maxFrequency(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int n = nums.size();
long long total = 0;
int l = 0, res = 1;
for (int r = 1; r < n; ++r) {
total += (long long)(nums[r] - nums[r - 1]) * (r - l);
while (total > k) {
total -= nums[r] - nums[l];
++l;
}
res = max(res, r - l + 1);
}
return res;
}
};
java 解法, 执行用时: 34 ms, 内存消耗: 54.2 MB, 提交时间: 2023-09-24 22:56:12
class Solution {
public int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
long total = 0;
int l = 0, res = 1;
for (int r = 1; r < n; ++r) {
total += (long) (nums[r] - nums[r - 1]) * (r - l);
while (total > k) {
total -= nums[r] - nums[l];
++l;
}
res = Math.max(res, r - l + 1);
}
return res;
}
}
python3 解法, 执行用时: 396 ms, 内存消耗: 27.3 MB, 提交时间: 2023-09-24 22:56:01
class Solution:
def maxFrequency(self, nums: List[int], k: int) -> int:
nums.sort()
n = len(nums)
l = 0
total = 0
res = 1
for r in range(1, n):
total += (nums[r] - nums[r - 1]) * (r - l)
while total > k:
total -= nums[r] - nums[l]
l += 1
res = max(res, r - l + 1)
return res
javascript 解法, 执行用时: 216 ms, 内存消耗: 54.9 MB, 提交时间: 2023-09-24 22:55:47
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var maxFrequency = function(nums, k) {
nums.sort((a, b) => a - b);
const n = nums.length;
let total = 0, res = 1, l = 0;
for (let r = 1; r < n; r++) {
total += (nums[r] - nums[r - 1]) * (r - l);
while (total > k) {
total -= nums[r] - nums[l];
l += 1;
}
res = Math.max(res, r - l + 1);
}
return res;
};
golang 解法, 执行用时: 232 ms, 内存消耗: 8.9 MB, 提交时间: 2023-09-24 22:55:30
// 排序+前缀和+二分左端点
func maxFrequency(a []int, k int) (ans int) {
sort.Ints(a)
sum := make([]int, len(a)+1)
for i, v := range a {
sum[i+1] = sum[i] + v
}
for r, v := range a {
l := sort.Search(r, func(l int) bool { return (r-l)*v-sum[r]+sum[l] <= k })
ans = max(ans, r-l+1)
}
return
}
// 排序 + 滑动窗口
func maxFrequency2(nums []int, k int) int {
sort.Ints(nums)
ans := 1
for l, r, total := 0, 1, 0; r < len(nums); r++ {
total += (nums[r] - nums[r-1]) * (r - l)
for total > k {
total -= nums[r] - nums[l]
l++
}
ans = max(ans, r-l+1)
}
return ans
}
func max(a, b int) int { if a > b { return a }; return b }