LeetCode 238周赛

发表于 | 分类于 |
字数统计: 626 | 阅读时长 ≈ 2

1838. 最高频元素的频数

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

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

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

样例：

1
2
3
4
输入：nums = [1,2,4], k = 5
输出：3
解释：对第一个元素执行 3 次递增操作，对第二个元素执 2 次递增操作，此时 nums = [4,4,4] 。
4 是数组中最高频元素，频数是 3 。

比赛的时候这道题目卡了一个小时，人没了

首先考虑排序，最终的答案一定是连续的一段区间，所有的数都等于最右边的数

一开始考虑二分，后来发现由于是滑动窗口，起点不固定，所以就没这么做了

打的时候一直觉得只要从两边往中间走，贪心的取较小的那个就可以

结果又难写，答案也不对

实际上这个贪心是不成立的，有可能后面会产生更小的情况

下面是正解，第一个做法是二分

还是一样的二分长度，遍历起点，找出满足条件的就可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int maxFrequency(vector<int>& nums, int k) {
  sort(nums.begin(), nums.end());
  vector<long long> pre(nums.size() + 10);
  for(int i = 1; i<= nums.size(); i++) {
    pre[i] = pre[i - 1] + nums[i - 1];
  }
  int l = 1, r = nums.size() + 1; 
  for(int i = 0; i < 100; i++) {
    long long mid = (l + r) / 2; 
    int flag = 0;
    for(int j = 0; j <= nums.size() - mid; j++) {
      if(nums[j + mid - 1] * mid - (pre[j + mid] - pre[j]) <= k){
        flag = 1;
        break;
      }
    }
    if(flag) 
      l = mid;
    else
      r = mid;
  }
  return l;
}

还有一种方法是官方题解的做法。

由于是滑动窗口，所以可以通过遍历右端点。

因为随着右端点向右移动，左端点一定是递增的。

每次遍历移动左端点，算出当前右端点下的最长长度，更新一下答案即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int maxFrequency(vector<int>& nums, int k) {
        long long res = 1, now = 0;
        int l = 0, len = nums.size();
        sort(nums.begin(), nums.end());
        // 滑动窗口解法
        for(long long r = 1; r < len; r++) {
            now += (nums[r] - nums[r - 1]) * (r - l);
            // 更新当前需要的次数
            while(now > k) {
                // 如果超过了k
                now -= (nums[r] - nums[l]);
                l++;
            }
            res = max(res, r - l + 1);
        }
        return res;
    }