1838. 最高频元素的频数--题解

发表于 分类于

1838. 最高频元素的频数

元素的 频数 是该元素在一个数组中出现的次数。

给你一个整数数组 nums 和一个整数 k 。在一步操作中，你可以选择 nums 的一个下标，并将该下标对应元素的值增加 1 。

执行最多 k 次操作后，返回数组中最高频元素的 最大可能频数 。

示例 1：

1
2
3
4
输入：nums = [1,2,4], k = 5
输出：3
解释：对第一个元素执行 3 次递增操作，对第二个元素执 2 次递增操作，此时 nums = [4,4,4] 。
4 是数组中最高频元素，频数是 3 。

示例 2：

1
2
3
4
5
6
输入：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：

1
2
输入：nums = [3,9,6], k = 2
输出：1

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105
  • 1 <= k <= 105

题解

总体思路采用滑动窗口的方式：

  1. 计算窗口内的差值，如果转变成最后一个值的变化数量小于 k 时，直接向后移动窗口
  2. 如果窗口的值大于 K 时，移动左侧指针，计算出最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func maxFrequency(nums []int, k int) int {
	sort.Ints(nums)
	start,sum := 0,0
	ans := 1
	for i := 1; i < len(nums); i++ {
         //计算差值
         //1,2,5  (2-1)*1+(5-2)*2=7.
         //此处需要多想一下
		sum += (nums[i] - nums[i-1]) * (i - start)
		for sum > k {
			sum -= nums[i] - nums[start]
			start++

		}
		if i-start+1 > ans {
			ans = i - start + 1
		}

	}
	return ans

}