apply-operations-to-maximize-frequency-score

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given a 0-indexed integer array <code>nums</code> and an integer <code>k</code>.

You can perform the following operation on the array at most <code>k</code> times:

<ul>
	<li>Choose any index <code>i</code> from the array and increase or decrease <code>nums[i]</code> by <code>1</code>.</li>
</ul>

The score of the final array is the frequency of the most frequent element in the array.

Return the maximum score you can achieve.

The frequency of an element is the number of occurences of that element in the array.

&nbsp;
Example 1:

<pre>
Input: nums = [1,2,6,4], k = 3
Output: 3
Explanation: We can do the following operations on the array:
- Choose i = 0, and increase the value of nums[0] by 1. The resulting array is [2,2,6,4].
- Choose i = 3, and decrease the value of nums[3] by 1. The resulting array is [2,2,6,3].
- Choose i = 3, and decrease the value of nums[3] by 1. The resulting array is [2,2,6,2].
The element 2 is the most frequent in the final array so our score is 3.
It can be shown that we cannot achieve a better score.
</pre>

Example 2:

<pre>
Input: nums = [1,4,4,2,4], k = 0
Output: 3
Explanation: We cannot apply any operations so our score will be the frequency of the most frequent element in the original array, which is 3.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
	<li><code>0 &lt;= k &lt;= 1014</code></li>
</ul>

第 376 场周赛

weekly-contest-376

maxFrequencyScore

高级专家

Apply Operations to Maximize Frequency Score

Frequency of the Most Frequent Element

frequency-of-the-most-frequent-element

最高频元素的频数

Array

Binary Search

Prefix Sum

Sorting

Sliding Window

给你一个下标从 0&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;。

你可以对数组执行 至多&nbsp;<code>k</code>&nbsp;次操作：

<ul>
	<li>从数组中选择一个下标 <code>i</code>&nbsp;，将&nbsp;<code>nums[i]</code> 增加&nbsp;或者&nbsp;减少&nbsp;<code>1</code>&nbsp;。</li>
</ul>

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

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

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

&nbsp;

示例 1：

<pre>
输入：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 是所有可行方案里的最大频率分数。
</pre>

示例 2：

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

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
	<li><code>0 &lt;= k &lt;= 1014</code></li>
</ul>