一、题目

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

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

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

点击查看原题
难度级别：中等

二、思路

1）排序+暴力搜索

由于对数字只进行增加1的操作，那么选定一个nums[i]后，只有对它小的数字进行操作才会增加其数量，所以先进行排序，这样比nums[i]小的元素都在其左侧，又由于每次只能增加1，那么根据贪心思想，肯定优先选择最大且小于nums[i]的元素
通过一次遍历，每个元素都向左搜索，找到最多能增加到nums[i]值的元素数量

2）排序+滑动窗口

根据上个方法的思想，其实不需要每次都对nums[i]左边重新进行搜索，计算最多能又多少个增加到nums[i]值的元素数量时，就已经统计了x个元素增加到nums[i]值的需要消耗多少次增加1，那么增加到nums[i+1]就是再消耗掉x*(nums[i+1]-nums[i])即可，设定两个左右指针，如果增加1的次数不够消耗，就左指针右移，将该位置消耗的增加1的次数返还即可

三、代码

1）排序+暴力搜索

  1. class Solution {
  2.     public int maxFrequency(int[] nums, int k) {
  3.         int ans = 0;
  4.         Arrays.sort(nums);
  5.         for (int i = nums.length - 1; i >= 0; i--) {
  6.             if (i != nums.length -1 && nums[i] == nums[i+1]) {
  7.                 continue;
  8.             }
  9.             int tempRecord = 1;    // 记录数量
  10.             int loc = i - 1;
  11.             int consume = k;
  12.             while (consume > 0 && loc >= 0) {    // 无可以增加的数量，或者搜索到最左边就退出
  13.                 int margin = nums[i] - nums[loc];
  14.                 consume -= margin;
  15.                 if (consume >= 0) {
  16.                     tempRecord++;
  17.                 }
  18.                 loc--;
  19.             }
  20.             ans = Math.max(ans, tempRecord);
  21.         }
  22.         return ans;
  23.     }
  24. }

时间复杂度为O(nlogn+kn)，空间复杂度为O(logn)

2）排序+滑动窗口

  1. class Solution {
  2.     public int maxFrequency(int[] nums, int k) {
  3.         int ans = 1;
  4.         int left = 0, consume = 0;
  5.         Arrays.sort(nums);
  6.         for (int right = 1; right < nums.length; right++) {
  7.             consume += (right - left) * (nums[right] - nums[right - 1]);
  8.             if (consume > k) {
  9.                 consume -= (nums[right] - nums[left]);
  10.                 left++;
  11.             }
  12.             ans = Math.max(ans, right - left + 1);
  13.         }
  14.         return ans;
  15.     }
  16. }

时间复杂度为O(nlogn)，空间复杂度为O(logn)