执行操作使频率分数最大
难度:
标签:
题目描述
You are given a 0-indexed integer array nums and an integer k.
You can perform the following operation on the array at most k times:
- Choose any index
ifrom the array and increase or decreasenums[i]by1.
The score of the final array is the frequency of the most frequent element in the array.
Return the maximum score you can achieve.
The frequency of an element is the number of occurences of that element in the array.
Example 1:
Input: nums = [1,2,6,4], k = 3 Output: 3 Explanation: We can do the following operations on the array: - Choose i = 0, and increase the value of nums[0] by 1. The resulting array is [2,2,6,4]. - Choose i = 3, and decrease the value of nums[3] by 1. The resulting array is [2,2,6,3]. - Choose i = 3, and decrease the value of nums[3] by 1. The resulting array is [2,2,6,2]. The element 2 is the most frequent in the final array so our score is 3. It can be shown that we cannot achieve a better score.
Example 2:
Input: nums = [1,4,4,2,4], k = 0 Output: 3 Explanation: We cannot apply any operations so our score will be the frequency of the most frequent element in the original array, which is 3.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1090 <= k <= 1014
代码结果
运行时间: 184 ms, 内存: 29.3 MB
/*
* 思路：
* 使用Java Streams对数组进行处理，实现与普通Java代码相同的逻辑。
*/
import java.util.Arrays;
import java.util.stream.IntStream;
public class SolutionStream {
public int maxFrequency(int[] nums, long k) {
int n = nums.length;
Arrays.sort(nums);
return IntStream.range(0, n)
.map(right -> {
int left = 0;
long totalCost = 0;
for (int i = 1; i <= right; i++) {
totalCost += (long) (nums[i] - nums[i - 1]) * (i - left);
while (totalCost > k) {
totalCost -= nums[i] - nums[left];
left++;
}
}
return right - left + 1;
})
.max()
.orElse(1);
}
}
解释
方法:
该题解采用双指针的方法。首先对数组进行排序，然后使用两个指针i和j，其中i初始化为0，j从0开始遍历数组。在遍历的过程中，计算如果将区间[i, j]内的所有元素增加到nums[(i+j)//2]所需要的操作次数，并用k减去这个操作次数。如果k小于0，说明当前的区间不能通过k次操作达到所有元素相等，此时需要移动左指针i，并相应地调整k的值。最终，区间[i, j]的长度即为可以通过至多k次操作得到的最大频率分数。
时间复杂度:
O(n log n)
空间复杂度:
O(1)
代码细节讲解
🦆
在题解中提到了对数组进行排序，排序后使用中位数作为目标值能否保证是最优的选择？
▷🦆
题解中的双指针方法在计算操作次数时，为什么选择`nums[(i+j)//2]`作为目标值？这样做的数学或逻辑依据是什么？
▷🦆
当操作次数k变为负数时，题解选择移动左指针i并调整k的值，请问这种调整方式是否总是可行的？存在什么潜在的风险或限制？
▷