【力扣题解】1838. 最高频元素的频数

😊博主目前也在学习，有错误欢迎指正😊
🌈保持热爱 奔赴星海🌈

文章目录

• • 一、题目
  • • 1、题目描述
    • 2、基础框架
    • 3、原题链接
  • 二、解题报告
  • • 1、思路分析
    • 2、代码详解
  • 三、本题知识

一、题目

1、题目描述

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

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

2、基础框架

• Java版本框架代码如下：

class Solution {    public int maxFrequency(int[] nums, int k) {    }}

3、原题链接

1838. 最高频元素的频数

二、解题报告

1、思路分析

       (1)定义一个sum数组，计算出nums数组的前缀和。
       (2)遍历sum数组，计算把i到j区间内的数都变成num[j]需要操作几次（设为s次），若s>k那么i++。当s<=k时，计算区间长度。每次遍历取最小值。

2、代码详解

class Solution {    public int maxFrequency(int[] nums, int k) { Arrays.sort(nums); int n = nums.length; int j = 0; int i = 0; int[] sum = new int[n + 1]; for(i = 1;i <= n;i++) {     sum[i] += sum[i - 1] + nums[i - 1]; } int ans = 0; i = 0; for(j = 1;j <= n;j++) {     long s = (sum[j] - sum[j - 1])*(j - i) - (sum[j] - sum[i]);     while(s > k) {  i++;  s = (sum[j] - sum[j - 1])*(j - i) - (sum[j] - sum[i]);     }     ans = Math.max(ans,j - i); } return ans;    }}

三、本题知识

前缀和