Description#
The frequency of an element is the number of times it occurs in an array.
You are given an integer array nums and an integer k. In one operation, you can choose an index of nums and increment the element at that index by 1.
Return the maximum possible frequency of an element after performing at most k operations.
Example 1:
Input: nums = [1,2,4], k = 5
Output: 3
Explanation: Increment the first element three times and the second element two times to make nums = [4,4,4].
4 has a frequency of 3.
Example 2:
Input: nums = [1,4,8,13], k = 5
Output: 2
Explanation: There are multiple optimal solutions:
- Increment the first element three times to make nums = [4,4,8,13]. 4 has a frequency of 2.
- Increment the second element four times to make nums = [1,8,8,13]. 8 has a frequency of 2.
- Increment the third element five times to make nums = [1,4,13,13]. 13 has a frequency of 2.
Example 3:
Input: nums = [3,9,6], k = 2
Output: 1
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1051 <= k <= 105
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution:
def maxFrequency(self, nums: List[int], k: int) -> int:
nums.sort()
l, r, n = 0, 1, len(nums)
ans, window = 1, 0
while r < n:
window += (nums[r] - nums[r - 1]) * (r - l)
while window > k:
window -= nums[r] - nums[l]
l += 1
r += 1
ans = max(ans, r - l)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
int ans = 1, window = 0;
for (int l = 0, r = 1; r < n; ++r) {
window += (nums[r] - nums[r - 1]) * (r - l);
while (window > k) {
window -= (nums[r] - nums[l++]);
}
ans = Math.max(ans, r - l + 1);
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int maxFrequency(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int n = nums.size();
int ans = 1;
long long window = 0;
for (int l = 0, r = 1; r < n; ++r) {
window += 1LL * (nums[r] - nums[r - 1]) * (r - l);
while (window > k) {
window -= (nums[r] - nums[l++]);
}
ans = max(ans, r - l + 1);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| func maxFrequency(nums []int, k int) int {
sort.Ints(nums)
ans, window := 1, 0
for l, r := 0, 1; r < len(nums); r++ {
window += (nums[r] - nums[r-1]) * (r - l)
for window > k {
window -= nums[r] - nums[l]
l++
}
ans = max(ans, r-l+1)
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| function maxFrequency(nums: number[], k: number): number {
nums.sort((a, b) => a - b);
let ans = 1;
let window = 0;
const n = nums.length;
for (let l = 0, r = 1; r < n; ++r) {
window += (nums[r] - nums[r - 1]) * (r - l);
while (window > k) {
window -= nums[r] - nums[l++];
}
ans = Math.max(ans, r - l + 1);
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| /**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var maxFrequency = function (nums, k) {
nums.sort((a, b) => a - b);
let ans = 1;
let window = 0;
const n = nums.length;
for (let l = 0, r = 1; r < n; ++r) {
window += (nums[r] - nums[r - 1]) * (r - l);
while (window > k) {
window -= nums[r] - nums[l++];
}
ans = Math.max(ans, r - l + 1);
}
return ans;
};
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution:
def maxFrequency(self, nums: List[int], k: int) -> int:
def check(cnt):
for i in range(n + 1 - cnt):
j = i + cnt - 1
if nums[j] * cnt - (s[j + 1] - s[i]) <= k:
return True
return False
nums.sort()
s = list(accumulate(nums, initial=0))
n = len(nums)
left, right = 1, n
while left < right:
mid = (left + right + 1) >> 1
if check(mid):
left = mid
else:
right = mid - 1
return left
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
private long[] s;
private int[] nums;
private int n;
private int k;
public int maxFrequency(int[] nums, int k) {
n = nums.length;
Arrays.sort(nums);
this.nums = nums;
this.s = new long[n + 1];
for (int i = 0; i < n; ++i) {
s[i + 1] = s[i] + nums[i];
}
this.k = k;
int left = 1, right = n;
while (left < right) {
int mid = (left + right + 1) >>> 1;
if (check(mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
private boolean check(int cnt) {
for (int i = 0; i < n + 1 - cnt; ++i) {
int j = i + cnt - 1;
if (1L * nums[j] * cnt - (s[j + 1] - s[i]) <= k) {
return true;
}
}
return false;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public:
int maxFrequency(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int n = nums.size();
long long s[n + 1];
s[0] = 0;
for (int i = 0; i < n; ++i) {
s[i + 1] = s[i] + nums[i];
}
int left = 1, right = n;
auto check = [&](int cnt) {
for (int i = 0; i < n + 1 - cnt; ++i) {
int j = i + cnt - 1;
if (1LL * nums[j] * cnt - (s[j + 1] - s[i]) <= k) {
return true;
}
}
return false;
};
while (left < right) {
int mid = (left + right + 1) >> 1;
if (check(mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| func maxFrequency(nums []int, k int) int {
sort.Ints(nums)
n := len(nums)
s := make([]int, n+1)
for i, x := range nums {
s[i+1] = s[i] + x
}
left, right := 1, n
check := func(cnt int) bool {
for i := 0; i < n+1-cnt; i++ {
j := i + cnt - 1
if nums[j]*cnt-(s[j+1]-s[i]) <= k {
return true
}
}
return false
}
for left < right {
mid := (left + right + 1) >> 1
if check(mid) {
left = mid
} else {
right = mid - 1
}
}
return left
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| function maxFrequency(nums: number[], k: number): number {
nums.sort((a, b) => a - b);
const n = nums.length;
const s = new Array(n + 1).fill(0);
for (let i = 0; i < n; ++i) {
s[i + 1] = s[i] + nums[i];
}
const check = (cnt: number) => {
for (let i = 0; i < n + 1 - cnt; ++i) {
const j = i + cnt - 1;
if (nums[j] * cnt - (s[j + 1] - s[i]) <= k) {
return true;
}
}
return false;
};
let left = 1;
let right = n;
while (left < right) {
const mid = (left + right + 1) >> 1;
if (check(mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| /**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var maxFrequency = function (nums, k) {
nums.sort((a, b) => a - b);
const n = nums.length;
const s = new Array(n + 1).fill(0);
for (let i = 0; i < n; ++i) {
s[i + 1] = s[i] + nums[i];
}
const check = cnt => {
for (let i = 0; i < n + 1 - cnt; ++i) {
const j = i + cnt - 1;
if (nums[j] * cnt - (s[j + 1] - s[i]) <= k) {
return true;
}
}
return false;
};
let left = 1;
let right = n;
while (left < right) {
const mid = (left + right + 1) >> 1;
if (check(mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
};
|
