What is the core approach for solving the Frequency of the Most Frequent Element problem?

The core approach is binary search over the frequency range combined with a sliding window technique to ensure that the number of operations used doesn't exceed `k`.

How does binary search help in solving this problem?

Binary search is used to explore the possible frequencies efficiently, narrowing down the search space by testing whether a given frequency can be achieved with at most `k` operations.

What role does the sliding window technique play in solving this problem?

The sliding window is used to find the subarray that can be transformed into the most frequent element within the allowed `k` operations. It efficiently checks potential solutions in linear time.

Can the problem be solved using brute force?

While a brute force approach is possible, it would be inefficient and fail to scale for large input sizes. The binary search and sliding window techniques significantly improve the solution's efficiency.

How does GhostInterview assist with this problem?

GhostInterview helps by providing a clear approach, breaking down the use of binary search and sliding window, and offering real-time problem-solving hints to avoid common pitfalls.

#1838

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

最高频元素的频数

元素的频数是该元素在一个数组中出现的次数。给你一个整数数组 nums 和一个整数 k 。在一步操作中，你可以选择 nums 的一个下标，并将该下标对应元素的值增加 1 。执行最多 k 次操作后，返回数组中最高频元素的最大可能频数。示例 1：输入： nums = [1,2,4], k …

数组二分查找贪心滑动窗口排序

题目描述

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

给你一个整数数组 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 <= 10⁵
1 <= nums[i] <= 10⁵
1 <= k <= 10⁵

lightbulb

解题思路

方法一：排序 + 前缀和 + 二分查找

根据题目描述，我们可以得出三个结论：

经过若干次操作后，数组中最高频元素一定是原数组中的某个元素。为什么呢？我们不妨假设操作的若干个元素分别为 $a_1, a_2, \cdots, a_m$ ，其中最大值为 $a_m$ ，这几个元素都变成了同一个值 $x$ ，其中 $x \geq a_m$ ，那么也一定可以将这些元素全部变成 $a_m$ ，这样操作次数不会增加。
操作的若干个元素一定是排序后的数组的一段连续子数组。
如果一个频数 $m$ 满足条件，那么所有 $m' \lt m$ 也满足条件。这启发我们可以考虑使用二分查找，找到最大的满足条件的频数。

因此，我们可以对数组 $nums$ 进行排序，然后计算排序后的数组的前缀和数组 $s$ ，其中 $s[i]$ 表示前 $i$ 个元素的和。

接下来，我们定义二分查找的左边界 $l=1$ ，右边界 $r=n$ 。每一次二分查找，我们取中间值 $m=(l+r+1)/2$ ，然后检查是否存在一个长度为 $m$ 的连续子数组，使得这个子数组中的元素都可以变成数组中的某个元素，且操作次数不超过 $k$ 。如果存在这样的子数组，那么我们就可以将左边界 $l$ 更新为 $m$ ，否则将右边界 $r$ 更新为 $m-1$ 。

最后返回左边界 $l$ 即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        def check(m: int) -> bool:
            for i in range(m, n + 1):
                if nums[i - 1] * m - (s[i] - s[i - m]) <= k:
                    return True
            return False

        n = len(nums)
        nums.sort()
        s = list(accumulate(nums, initial=0))
        l, r = 1, n
        while l < r:
            mid = (l + r + 1) >> 1
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return l

speed

复杂度分析

指标	值
时间	O(n \cdot \log{}n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Ability to combine binary search and greedy techniques to solve a problem with constraints on operations.
question_mark
Demonstrates understanding of sliding window techniques in optimizing search spaces and reducing redundant computations.
question_mark
Effective handling of array manipulation while maintaining clarity in approach and efficiency.

warning

常见陷阱

外企场景

error
Failing to handle the sliding window efficiently, resulting in excessive computations or incorrect frequency checks.
error
Misunderstanding the binary search space, leading to suboptimal choices for the maximum frequency.
error
Incorrectly handling the number of operations `k`, either exceeding it or failing to utilize it optimally.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the number of operations `k` is reduced to 0? This would change the problem to a simple frequency counting problem.
arrow_right_alt
What if instead of incrementing elements, you were allowed to decrement them? This could require reversing the logic of the solution.
arrow_right_alt
How would the solution change if the array contained only unique elements?

help

常见问题

外企场景

继续练习

#2271 毯子覆盖的最多白色砖块数 #2234 花园的最大总美丽值 #3413 收集连续 K 个袋子可以获得的最多硬币数量