1838. 最高频元素的频数#

题目描述#

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

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

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

核心思想#

排序 + 不定长滑动窗口。

只能增加，不能减少，因此最高频元素一定是数组中的某个元素，且要将它前面的元素提升到它的值。

排序后，用滑动窗口维护一个区间，区间内所有元素都能在 k 次操作内变成 nums[right]（窗口最大值）。

判断条件：nums[right] * 窗口长度 - 窗口和 <= k

算法步骤#

排序 nums
初始化 left = 0, window_sum = 0, ans = 0
遍历 right 从 0 到 n-1：
- window_sum += nums[right]
- 当 nums[right] * (right - left + 1) - window_sum > k 时：
  - window_sum -= nums[left], left += 1
- ans = max(ans, right - left + 1)
返回 ans

逐步举例#

以 nums = [1, 2, 4], k = 5 为例（已排序）：

right	nums[right]	window_sum	窗口长度	操作数	>5?	收缩	ans
0	1	1	1	1*1-1=0	否	—	1
1	2	3	2	2*2-3=1	否	—	2
2	4	7	3	4*3-7=5	否	—	3

最终 ans = 3。

验证：将 [1, 2] 都变成 4，需要 (4-1) + (4-2) = 3 + 2 = 5 次操作 ✓。

复杂度分析#

时间复杂度：O(n log n)。排序 O(n log n)，滑动窗口 O(n)。
空间复杂度：O(1)（忽略排序的栈空间）。

参考#

灵茶山艾府：最高频元素的频数

代码实现#

1
from typing import List
2

3

4
class Solution:
5
    def maxFrequency(self, nums: List[int], k: int) -> int:
6
        nums.sort()
7
        n = len(nums)
8
        ans = left = 0
9
        window_sum = 0
10
        for right in range(n):
11
            window_sum += nums[right]
12
            while nums[right] * (right - left + 1) - window_sum > k:
13
                window_sum -= nums[left]
14
                left += 1
15
            ans = max(ans, right - left + 1)
16
        return ans

1
import sys
2
import unittest
3
from pathlib import Path
4

5
sys.path.insert(0, str(Path(__file__).parent))
6

7
from solution import Solution
8

9

10
class TestMaxFrequency(unittest.TestCase):
11
    def test_example1(self):
12
        nums = [1, 2, 4]
13
        k = 5
14
        self.assertEqual(Solution().maxFrequency(nums, k), 3)
15

16
    def test_example2(self):
17
        nums = [1, 4, 8, 13]
18
        k = 5
19
        self.assertEqual(Solution().maxFrequency(nums, k), 2)
20

21
    def test_example3(self):
22
        nums = [3, 9, 6]
23
        k = 2
24
        self.assertEqual(Solution().maxFrequency(nums, k), 1)
25

26
    def test_single(self):
27
        nums = [5]
28
        k = 0
29
        self.assertEqual(Solution().maxFrequency(nums, k), 1)
30

31
    def test_all_same(self):
32
        nums = [1, 1, 1, 1]
33
        k = 0
34
        self.assertEqual(Solution().maxFrequency(nums, k), 4)
35

36
    def test_k_zero(self):
37
        nums = [1, 2, 3, 4]
38
        k = 0
39
        self.assertEqual(Solution().maxFrequency(nums, k), 1)
40

41
    def test_large_k(self):
42
        nums = [1, 2, 3, 4]
43
        k = 100
44
        self.assertEqual(Solution().maxFrequency(nums, k), 4)
45

46

47
if __name__ == "__main__":
48
    unittest.main()