同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
元素的 频数 是该元素在一个数组中出现的次数。
给你一个整数数组 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 <= 105
1 <= nums[i] <= 105
1 <= k <= 105
我们可以先对数组 $nums$ 进行排序,然后枚举每个数作为最高频元素,用滑动窗口维护下标 $l$ 到 $r$ 的数都增加到 $nums[r]$ 的操作次数。如果操作次数大于 $k$,则窗口左端右移,直到操作次数小于等于 $k$。这样,我们就可以求出以每个数为最高频元素的最大频数。
时间复杂度 $O(n \times \log n)$,空间复杂度 $O(\log n)$。其中 $n$ 为数组 $nums$ 的长度。
class Solution:
def maxFrequency(self, nums: List[int], k: int) -> int:
nums.sort()
l, r, n = 0, 1, len(nums)
ans, window = 1, 0
while r < n:
window += (nums[r] - nums[r - 1]) * (r - l)
while window > k:
window -= nums[r] - nums[l]
l += 1
r += 1
ans = max(ans, r - l)
return ans
class Solution {
public int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
int ans = 1, window = 0;
for (int l = 0, r = 1; r < n; ++r) {
window += (nums[r] - nums[r - 1]) * (r - l);
while (window > k) {
window -= (nums[r] - nums[l++]);
}
ans = Math.max(ans, r - l + 1);
}
return ans;
}
}
class Solution {
public:
int maxFrequency(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int n = nums.size();
int ans = 1;
long long window = 0;
for (int l = 0, r = 1; r < n; ++r) {
window += 1LL * (nums[r] - nums[r - 1]) * (r - l);
while (window > k) {
window -= (nums[r] - nums[l++]);
}
ans = max(ans, r - l + 1);
}
return ans;
}
};
func maxFrequency(nums []int, k int) int {
sort.Ints(nums)
ans, window := 1, 0
for l, r := 0, 1; r < len(nums); r++ {
window += (nums[r] - nums[r-1]) * (r - l)
for window > k {
window -= nums[r] - nums[l]
l++
}
ans = max(ans, r-l+1)
}
return ans
}
function maxFrequency(nums: number[], k: number): number {
nums.sort((a, b) => a - b);
let ans = 1;
let window = 0;
const n = nums.length;
for (let l = 0, r = 1; r < n; ++r) {
window += (nums[r] - nums[r - 1]) * (r - l);
while (window > k) {
window -= nums[r] - nums[l++];
}
ans = Math.max(ans, r - l + 1);
}
return ans;
}
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var maxFrequency = function (nums, k) {
nums.sort((a, b) => a - b);
let ans = 1;
let window = 0;
const n = nums.length;
for (let l = 0, r = 1; r < n; ++r) {
window += (nums[r] - nums[r - 1]) * (r - l);
while (window > k) {
window -= nums[r] - nums[l++];
}
ans = Math.max(ans, r - l + 1);
}
return ans;
};
我们观察发现,如果一个区间长度 $cnt$ 满足条件,那么区间长度小于 $cnt$ 的也一定满足条件。因此,我们可以使用二分查找的方法,找到最大的且满足条件的区间长度。
在二分查找之前,我们需要对数组 $nums[r]$ 进行排序,然后计算出数组 $nums[r]$ 的前缀和数组 $s$,其中 $s[i]$ 表示数组 $nums[r]$ 前 $i$ 个数的和。这样,我们就可以在 $O(1)$ 的时间内求出区间 $[i, j]$ 的和为 $s[j + 1] - s[i]$。
接下来,我们定义二分的左边界 $left=1$, $right=n$。然后二分枚举区间长度 $mid$,如果当前区间长度 $mid$ 满足条件,那么我们就更新二分的左边界为 $mid$,否则更新二分的右边界为 $mid-1$。最后,我们返回二分的左边界即可。
问题转换为如何判断区间长度为 $cnt$ 的区间是否满足条件。我们在 $[0,..n-cnt]$ 范围内枚举左端点 $i$,那么此时区间的右端点 $j = i + cnt - 1$。要把区间内的所有数都增加到 $nums[j]$,需要的操作次数为 $nums[j] \times cnt - (s[j + 1] - s[i])$。如果这个操作次数小于等于 $k$,那么说明区间长度为 $cnt$ 的区间满足条件,返回 true
。否则枚举结束,返回 false
。
时间复杂度 $O(n \times \log n)$,空间复杂度 $O(n)$。其中 $n$ 为数组 $nums$ 的长度。
class Solution:
def maxFrequency(self, nums: List[int], k: int) -> int:
def check(cnt):
for i in range(n + 1 - cnt):
j = i + cnt - 1
if nums[j] * cnt - (s[j + 1] - s[i]) <= k:
return True
return False
nums.sort()
s = list(accumulate(nums, initial=0))
n = len(nums)
left, right = 1, n
while left < right:
mid = (left + right + 1) >> 1
if check(mid):
left = mid
else:
right = mid - 1
return left
class Solution {
private long[] s;
private int[] nums;
private int n;
private int k;
public int maxFrequency(int[] nums, int k) {
n = nums.length;
Arrays.sort(nums);
this.nums = nums;
this.s = new long[n + 1];
for (int i = 0; i < n; ++i) {
s[i + 1] = s[i] + nums[i];
}
this.k = k;
int left = 1, right = n;
while (left < right) {
int mid = (left + right + 1) >>> 1;
if (check(mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
private boolean check(int cnt) {
for (int i = 0; i < n + 1 - cnt; ++i) {
int j = i + cnt - 1;
if (1L * nums[j] * cnt - (s[j + 1] - s[i]) <= k) {
return true;
}
}
return false;
}
}
class Solution {
public:
int maxFrequency(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int n = nums.size();
long long s[n + 1];
s[0] = 0;
for (int i = 0; i < n; ++i) {
s[i + 1] = s[i] + nums[i];
}
int left = 1, right = n;
auto check = [&](int cnt) {
for (int i = 0; i < n + 1 - cnt; ++i) {
int j = i + cnt - 1;
if (1LL * nums[j] * cnt - (s[j + 1] - s[i]) <= k) {
return true;
}
}
return false;
};
while (left < right) {
int mid = (left + right + 1) >> 1;
if (check(mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
};
func maxFrequency(nums []int, k int) int {
sort.Ints(nums)
n := len(nums)
s := make([]int, n+1)
for i, x := range nums {
s[i+1] = s[i] + x
}
left, right := 1, n
check := func(cnt int) bool {
for i := 0; i < n+1-cnt; i++ {
j := i + cnt - 1
if nums[j]*cnt-(s[j+1]-s[i]) <= k {
return true
}
}
return false
}
for left < right {
mid := (left + right + 1) >> 1
if check(mid) {
left = mid
} else {
right = mid - 1
}
}
return left
}
function maxFrequency(nums: number[], k: number): number {
nums.sort((a, b) => a - b);
const n = nums.length;
const s = new Array(n + 1).fill(0);
for (let i = 0; i < n; ++i) {
s[i + 1] = s[i] + nums[i];
}
const check = (cnt: number) => {
for (let i = 0; i < n + 1 - cnt; ++i) {
const j = i + cnt - 1;
if (nums[j] * cnt - (s[j + 1] - s[i]) <= k) {
return true;
}
}
return false;
};
let left = 1;
let right = n;
while (left < right) {
const mid = (left + right + 1) >> 1;
if (check(mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var maxFrequency = function (nums, k) {
nums.sort((a, b) => a - b);
const n = nums.length;
const s = new Array(n + 1).fill(0);
for (let i = 0; i < n; ++i) {
s[i + 1] = s[i] + nums[i];
}
const check = cnt => {
for (let i = 0; i < n + 1 - cnt; ++i) {
const j = i + cnt - 1;
if (nums[j] * cnt - (s[j + 1] - s[i]) <= k) {
return true;
}
}
return false;
};
let left = 1;
let right = n;
while (left < right) {
const mid = (left + right + 1) >> 1;
if (check(mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
};
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。