执行操作使频率分数最大

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

难度: Hard

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

你可以对数组执行 至多 k 次操作：

  • 从数组中选择一个下标 i ，将 nums[i] 增加 或者 减少 1 。

最终数组的频率分数定义为数组中众数的 频率 。

请你返回你可以得到的 最大 频率分数。

众数指的是数组中出现次数最多的数。一个元素的频率指的是数组中这个元素的出现次数。

示例 1：

输入：nums = [1,2,6,4], k = 3
输出：3
解释：我们可以对数组执行以下操作：
- 选择 i = 0 ，将 nums[0] 增加 1 。得到数组 [2,2,6,4] 。
- 选择 i = 3 ，将 nums[3] 减少 1 ，得到数组 [2,2,6,3] 。
- 选择 i = 3 ，将 nums[3] 减少 1 ，得到数组 [2,2,6,2] 。
元素 2 是最终数组中的众数，出现了 3 次，所以频率分数为 3 。
3 是所有可行方案里的最大频率分数。

示例 2：

输入：nums = [1,4,4,2,4], k = 0
输出：3
解释：我们无法执行任何操作，所以得到的频率分数是原数组中众数的频率 3 。

提示：

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

Submission

运行时间: 184 ms

内存: 29.3 MB

# class Solution:
#     def maxFrequencyScore(self, nums: List[int], k: int) -> int:
#         n = len(nums)
#         nums.sort()

#         pre = [0]
#         s = 0
#         for i in range(n):
#             s += nums[i]
#             pre.append(s)

#         left, right = 1, n
#         while right > left:
#             l = left + right + 1 >> 1
#             flag = l & 1
#             for i in range(n - l + 1):
#                 cur = i + (l - 1 >> 1)
#                 if nums[cur] * (- 2 + flag) - 2 * pre[cur] + pre[i] + pre[i + l] <= k:
#                     left = l
#                     break
#             else:
#                 right = l - 1

#         return left

# 双指针
class Solution:
    def maxFrequencyScore(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums.sort()
        i = 0

        for j in range(n):
            k -= nums[j] - nums[(i + j) // 2]
            if k < 0:
                k += nums[(i + j + 1) // 2] - nums[i]
                i += 1

        return n - i

Explain

该题解采用双指针的方法。首先对数组进行排序，然后使用两个指针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)

# 双指针

class Solution:
    def maxFrequencyScore(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums.sort()  # 对数组进行排序
        i = 0  # 左指针

        for j in range(n):  # 遍历数组
            k -= nums[j] - nums[(i + j) // 2]  # 计算区间[i, j]内元素增加到nums[(i+j)//2]所需的操作次数
            if k < 0:  # 如果操作次数超过k
                k += nums[(i + j + 1) // 2] - nums[i]  # 调整k的值
                i += 1  # 移动左指针

        return n - i  # 返回区间长度，即最大频率分数

Explore

在题解中，排序后使用中位数作为目标值是为了最小化总的操作次数，使所有元素变为同一个值。数学上，中位数是最小化所有数据点到一个共同点的距离总和的最佳选择。这是因为中位数将数据分为两个大小大致相等的部分，从而减少了向这个值调整的总距离。在这个问题的具体背景下，使用中位数来逼近可以确保用最少的操作次数将尽可能多的元素调整到这个值，从而最大化频率分数。

在使用双指针策略时，选择`nums[(i+j)//2]`作为目标值是出于减少总操作次数的考虑。当数组已排序时，中间的值（或中位数）是将所有值合并到一个点所需总调整距离最小的选择。因此，当计算区间[i, j]内所有元素变为相同值所需的最少操作次数时，选择中间的值作为目标可以确保在给定的操作次数k内，达到可能的最大区间长度。这种方法利用了排序数组中值的顺序和中位数减少总调整距离的特性，使得在限定操作次数内，可以尽可能扩大相同元素的频率。

当操作次数k变为负数时，意味着当前区间[i, j]不能仅通过k次操作使所有元素相等。这时移动左指针i是为了减少区间长度，尝试找到一个新的可行区间。通过调整k的值，即减去区间左端点的变化带来的操作数量变化，可以重新评估新的区间是否可行。这种调整方式通常是可行的，因为它通过缩小问题规模来寻找解决方案。然而，潜在的风险包括可能过早地缩小区间，尤其是在k的值本身就较小的情况下，这可能导致未能找到最优的最长区间。此外，如果所有元素差异较大，频繁地调整k和移动指针可能导致效率低下。