最高频元素的频数

标签: 贪心 数组 二分查找 前缀和 排序 滑动窗口

难度: Medium

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

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

Submission

运行时间: 247 ms

内存: 26.4 MB

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums.sort()
        if n == 1:
            return 1
        l,r,ans,s = 0,1,0,0
        while r < n:
            s += (r-l)*(nums[r]-nums[r-1])
            if s > k:
                ans = max(ans,r-l)
                while s > k:
                    s -= nums[r] - nums[l]
                    l += 1
            r += 1
        ans = max(ans,r-l)
        return ans

Explain

该题解使用了滑动窗口的思路。首先对数组进行排序，然后使用两个指针l和r表示窗口的左右边界。变量s存储为了使窗口内所有元素值相同所需的总增量。窗口扩展时，若s不超过k，右指针r向右移动；若s超过k，左指针l向右移动以缩小窗口，直到s不超过k。每次移动指针时，都会更新最大频率的可能值ans。这个方法依靠排序后的数组特性，保证窗口内的值可以通过增加操作转变为窗口右端的值。

时间复杂度: O(n log n)

空间复杂度: O(1)

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums.sort()
        if n == 1:
            return 1
        l, r, ans, s = 0, 1, 0, 0
        while r < n:
            s += (r - l) * (nums[r] - nums[r - 1])  # 增加s以反映新元素到窗口的差距总和
            while s > k:
                ans = max(ans, r - l)
                s -= nums[r] - nums[l]  # 调整窗口左边界，减少s
                l += 1
            r += 1
        ans = max(ans, r - l)  # 最后一次检查窗口大小
        return ans

Explore

在题解中，s代表为了使窗口内所有元素的值都等于窗口内最右端的元素值所需的总增量。具体计算方式是，每当右指针r向右移动以包含一个新的元素时，计算新增元素与窗口最右端之前的元素的差值，然后乘以窗口当前的宽度(即r-l)，加到s上。这是因为，窗口内每个旧元素都需要增加这个差值才能与新的最右端元素对齐。当s超过允许的最大值k时，需要通过移动左指针l向右来缩小窗口，每向右移动一次，减去的值是窗口最左端的元素与新的最左端元素的差值，因为窗口缩小后，这部分增量不再需要。

当s超过k时，表示窗口内的元素不能全部通过增加操作转变为窗口右端的值。在这种情况下，我们需要减少s以满足s<=k的条件。移动左指针l是最直接有效的方式来减少s，因为这会直接减少窗口的大小，相应地减少需要变更的元素数量。此外，移动右指针r以缩小窗口并不合适，因为这样做会损失掉窗口的扩展潜力，减少最大频率的可能性。

通过数组排序，我们可以确保窗口内的元素是有序的，这意味着窗口右端的值是窗口内最大的。因此，将所有窗口内的元素增加到窗口右端的值，总增量s会是最小的。如果选择将窗口内的元素变为其他非最右端的值，总增量s将会更大，因为窗口内更多的元素需要更大的增量来达到新的目标值。因此，排序后选择最右端的值作为目标是最优的策略，因为这样可以最小化所需的总增量s。