class Solution {
public:
int maxFrequencyScore(vector<int>& nums, long long k) {
}
};
100123. 执行操作使频率分数最大
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
你可以对数组执行 至多 k 次操作：
i ，将 nums[i] 增加 或者 减少 1 。最终数组的频率分数定义为数组中众数的 频率 。
请你返回你可以得到的 最大 频率分数。
众数指的是数组中出现次数最多的数。一个元素的频率指的是数组中这个元素的出现次数。
示例 1：
输入：nums = [1,2,6,4], k = 3 输出：3 解释：我们可以对数组执行以下操作： - 选择 i = 0 ，将 nums[0] 增加 1 。得到数组 [2,2,6,4] 。 - 选择 i = 3 ，将 nums[3] 减少 1 ，得到数组 [2,2,6,3] 。 - 选择 i = 3 ，将 nums[3] 减少 1 ，得到数组 [2,2,6,2] 。 元素 2 是最终数组中的众数，出现了 3 次，所以频率分数为 3 。 3 是所有可行方案里的最大频率分数。
示例 2：
输入：nums = [1,4,4,2,4], k = 0 输出：3 解释：我们无法执行任何操作，所以得到的频率分数是原数组中众数的频率 3 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 1090 <= k <= 1014原站题解
golang 解法, 执行用时: 132 ms, 内存消耗: 9.2 MB, 提交时间: 2023-12-17 23:40:51
// 滑动窗口 + 前缀和
func maxFrequencyScore(nums []int, K int64) (ans int) {
k := int(K)
slices.Sort(nums)
n := len(nums)
sum := make([]int, n+1)
for i, v := range nums {
sum[i+1] = sum[i] + v
}
// 把 nums[l] 到 nums[r] 都变成 nums[i]
distanceSum := func(l, i, r int) int {
left := nums[i]*(i-l) - (sum[i] - sum[l])
right := sum[r+1] - sum[i+1] - nums[i]*(r-i)
return left + right
}
left := 0
for i := range nums {
for distanceSum(left, (left+i)/2, i) > k {
left++
}
ans = max(ans, i-left+1)
}
return
}
// 滑动窗口 + 贡献法
func maxFrequencyScore2(nums []int, k int64) int {
slices.Sort(nums)
ans, left := 0, 0
s := int64(0) // 窗口元素与窗口中位数的差之和
for right, x := range nums {
s += int64(x - nums[(left+right)/2])
for s > k {
s += int64(nums[left] - nums[(left+right+1)/2])
left++
}
ans = max(ans, right-left+1)
}
return ans
}
cpp 解法, 执行用时: 160 ms, 内存消耗: 83.4 MB, 提交时间: 2023-12-17 23:41:27
class Solution {
public:
int maxFrequencyScore(vector<int> &nums, long long k) {
sort(nums.begin(), nums.end());
int ans = 0, left = 0;
long long s = 0; // 窗口元素与窗口中位数的差之和
for (int right = 0; right < nums.size(); right++) {
s += nums[right] - nums[(left + right) / 2];
while (s > k) {
s += nums[left] - nums[(left + right + 1) / 2];
left++;
}
ans = max(ans, right - left + 1);
}
return ans;
}
int maxFrequencyScore2(vector<int> &nums, long long k) {
sort(nums.begin(), nums.end());
int n = nums.size();
vector<long long> s(n + 1, 0);
for (int i = 0; i < n; i++) {
s[i + 1] = s[i] + nums[i];
}
// 把 nums[l] 到 nums[r] 都变成 nums[i]
auto distance_sum = [&](int l, int i, int r) -> long long {
long long left = (long long) nums[i] * (i - l) - (s[i] - s[l]);
long long right = s[r + 1] - s[i + 1] - (long long) nums[i] * (r - i);
return left + right;
};
int ans = 0, left = 0;
for (int i = 0; i < n; i++) {
while (distance_sum(left, (left + i) / 2, i) > k) {
left++;
}
ans = max(ans, i - left + 1);
}
return ans;
}
};
java 解法, 执行用时: 38 ms, 内存消耗: 59.7 MB, 提交时间: 2023-12-17 23:42:03
class Solution {
public int maxFrequencyScore(int[] nums, long k) {
Arrays.sort(nums);
int n = nums.length;
long[] s = new long[n + 1];
for (int i = 0; i < n; i++) {
s[i + 1] = s[i] + nums[i];
}
int ans = 0, left = 0;
for (int i = 0; i < n; i++) {
while (distanceSum(s, nums, left, (left + i) / 2, i) > k) {
left++;
}
ans = Math.max(ans, i - left + 1);
}
return ans;
}
// 把 nums[l] 到 nums[r] 都变成 nums[i]
long distanceSum(long[] s, int[] nums, int l, int i, int r) {
long left = (long) nums[i] * (i - l) - (s[i] - s[l]);
long right = s[r + 1] - s[i + 1] - (long) nums[i] * (r - i);
return left + right;
}
public int maxFrequencyScore2(int[] nums, long k) {
Arrays.sort(nums);
int ans = 0, left = 0;
long s = 0; // 窗口元素与窗口中位数的差之和
for (int right = 0; right < nums.length; right++) {
s += nums[right] - nums[(left + right) / 2];
while (s > k) {
s += nums[left] - nums[(left + right + 1) / 2];
left++;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
python3 解法, 执行用时: 312 ms, 内存消耗: 29.8 MB, 提交时间: 2023-12-17 23:43:08
class Solution:
# 滑动窗口 + 贡献法
def maxFrequencyScore(self, nums: List[int], k: int) -> int:
nums.sort()
ans = left = s = 0 # s 是窗口元素与窗口中位数的差之和
for right, x in enumerate(nums):
s += x - nums[(left + right) // 2]
while s > k:
s += nums[left] - nums[(left + right + 1) // 2]
left += 1
ans = max(ans, right - left + 1)
return ans
# 滑动窗口 + 前缀和
def maxFrequencyScore2(self, nums: List[int], k: int) -> int:
nums.sort()
n = len(nums)
s = list(accumulate(nums, initial=0)) # nums 的前缀和
# 把 nums[l] 到 nums[r] 都变成 nums[i]
def distance_sum(l: int, i: int, r: int) -> int:
left = nums[i] * (i - l) - (s[i] - s[l])
right = s[r + 1] - s[i + 1] - nums[i] * (r - i)
return left + right
ans = left = 0
for i in range(n):
while distance_sum(left, (left + i) // 2, i) > k:
left += 1
ans = max(ans, i - left + 1)
return ans