描述

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

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

样例

  1. 示例 1：
  3. 输入：nums = [1,2,4], k = 5
  4. 输出：3
  5. 解释：对第一个元素执行 3 次递增操作，对第二个元素执 2 次递增操作，此时 nums = [4,4,4] 。
  6. 4 是数组中最高频元素，频数是 3 。
  8. 示例 2：
  10. 输入：nums = [1,4,8,13], k = 5
  11. 输出：2
  12. 解释：存在多种最优解决方案：
  13. - 对第一个元素执行 3 次递增操作，此时 nums = [4,4,8,13] 。4 是数组中最高频元素，频数是 2 。
  14. - 对第二个元素执行 4 次递增操作，此时 nums = [1,8,8,13] 。8 是数组中最高频元素，频数是 2 。
  15. - 对第三个元素执行 5 次递增操作，此时 nums = [1,4,13,13] 。13 是数组中最高频元素，频数是 2 。
  17. 示例 3：
  19. 输入：nums = [3,9,6], k = 2
  20. 输出：1

提示

  1. 1 <= nums.length <= 105
  2. 1 <= nums[i] <= 105
  3. 1 <= k <= 105

解题思路

排序 + 前缀和 + 二分 + 滑动窗口

  • 对原数组 nums 进行从小到大排序
  • 二分答案 lenlen 作为窗口长度
  • 利用前缀和计算真实区间的和
  • 比较目标区间和和真实区间和的差值

AC代码

  1. class Solution {
  2.     int[] nums, sum;
  3.     int n, k;
  4.     public int maxFrequency(int[] _nums, int _k) {
  5.         nums = _nums;
  6.         k = _k;
  7.         n = nums.length;
  8.         Arrays.sort(nums);
  9.         sum = new int[n + 1];
  10.         for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
  11.         int l = 0, r = n;
  12.         while (l < r) {
  13.             int mid = l + r + 1 >> 1;
  14.             if (check(mid)) l = mid;
  15.             else r = mid - 1;
  16.         }
  17.         return r;
  18.     }
  19.     boolean check(int len) {
  20.         for (int l = 0; l + len - 1 < n; l++) {
  21.             int r = l + len - 1;
  22.             int cur = sum[r + 1] - sum[l];
  23.             int t = nums[r] * len;
  24.             if (t - cur <= k) return true;
  25.         }
  26.         return false;
  27.     }
  28. }

时间复杂度

  • 时间复杂度：排序的复杂度为 O(nlogn)；计算前缀和数组复杂度为 O(n)；check 函数的复杂度为O(n)，因此二分复杂度为 O(nlogn)。整体复杂度为 O(nlogn)
  • 空间复杂度：O(n)