Description
You are given an integer array nums
and two integers k
and numOperations
.
You must perform an operation numOperations
times on nums
, where in each operation you:
- Select an index
i
that was not selected in any previous operations.
- Add an integer in the range
[-k, k]
to nums[i]
.
Return the maximum possible frequency of any element in nums
after performing the operations.
Example 1:
Input: nums = [1,4,5], k = 1, numOperations = 2
Output: 2
Explanation:
We can achieve a maximum frequency of two by:
- Adding 0 to
nums[1]
. nums
becomes [1, 4, 5]
.
- Adding -1 to
nums[2]
. nums
becomes [1, 4, 4]
.
Example 2:
Input: nums = [5,11,20,20], k = 5, numOperations = 1
Output: 2
Explanation:
We can achieve a maximum frequency of two by:
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 105
0 <= k <= 105
0 <= numOperations <= nums.length
Solutions
Solution 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | class Solution:
def maxFrequency(self, nums: List[int], k: int, numOperations: int) -> int:
cnt = defaultdict(int)
d = defaultdict(int)
for x in nums:
cnt[x] += 1
d[x] += 0
d[x - k] += 1
d[x + k + 1] -= 1
ans = s = 0
for x, t in sorted(d.items()):
s += t
ans = max(ans, min(s, cnt[x] + numOperations))
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution {
public int maxFrequency(int[] nums, int k, int numOperations) {
Map<Integer, Integer> cnt = new HashMap<>();
TreeMap<Integer, Integer> d = new TreeMap<>();
for (int x : nums) {
cnt.merge(x, 1, Integer::sum);
d.putIfAbsent(x, 0);
d.merge(x - k, 1, Integer::sum);
d.merge(x + k + 1, -1, Integer::sum);
}
int ans = 0, s = 0;
for (var e : d.entrySet()) {
int x = e.getKey(), t = e.getValue();
s += t;
ans = Math.max(ans, Math.min(s, cnt.getOrDefault(x, 0) + numOperations));
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public:
int maxFrequency(vector<int>& nums, int k, int numOperations) {
unordered_map<int, int> cnt;
map<int, int> d;
for (int x : nums) {
cnt[x]++;
d[x];
d[x - k]++;
d[x + k + 1]--;
}
int ans = 0, s = 0;
for (const auto& [x, t] : d) {
s += t;
ans = max(ans, min(s, cnt[x] + numOperations));
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | func maxFrequency(nums []int, k int, numOperations int) (ans int) {
cnt := make(map[int]int)
d := make(map[int]int)
for _, x := range nums {
cnt[x]++
d[x] = d[x]
d[x-k]++
d[x+k+1]<
|