| comments | difficulty | edit_url | rating | source | tags | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
true |
Medium |
1876 |
Weekly Contest 238 Q2 |
|
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
According to the problem description, we can draw three conclusions:
- After several operations, the element with the highest frequency in the array must be an element in the original array. Why? Suppose the elements operated are
$a_1, a_2, \cdots, a_m$ , where the maximum is$a_m$ . These elements have all been changed to the same value$x$ , where$x \geq a_m$ . Then we can also change these elements all to$a_m$ , and the number of operations will not increase. - The elements operated must be a continuous subarray in the sorted array.
- If a frequency
$m$ satisfies the condition, then all$m' < m$ also satisfy the condition. This inspires us to consider using binary search to find the maximum frequency that satisfies the condition.
Therefore, we can sort the array
Next, we define the left boundary of the binary search as
Finally, return the left boundary
The time complexity is
class Solution:
def maxFrequency(self, nums: List[int], k: int) -> int:
def check(m: int) -> bool:
for i in range(m, n + 1):
if nums[i - 1] * m - (s[i] - s[i - m]) <= k:
return True
return False
n = len(nums)
nums.sort()
s = list(accumulate(nums, initial=0))
l, r = 1, n
while l < r:
mid = (l + r + 1) >> 1
if check(mid):
l = mid
else:
r = mid - 1
return lclass Solution {
private int[] nums;
private long[] s;
private int k;
public int maxFrequency(int[] nums, int k) {
this.k = k;
this.nums = nums;
Arrays.sort(nums);
int n = nums.length;
s = new long[n + 1];
for (int i = 1; i <= n; ++i) {
s[i] = s[i - 1] + nums[i - 1];
}
int l = 1, r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
private boolean check(int m) {
for (int i = m; i <= nums.length; ++i) {
if (1L * nums[i - 1] * m - (s[i] - s[i - m]) <= k) {
return true;
}
}
return false;
}
}class Solution {
public:
int maxFrequency(vector<int>& nums, int k) {
int n = nums.size();
sort(nums.begin(), nums.end());
long long s[n + 1];
s[0] = 0;
for (int i = 1; i <= n; ++i) {
s[i] = s[i - 1] + nums[i - 1];
}
int l = 1, r = n;
auto check = [&](int m) {
for (int i = m; i <= n; ++i) {
if (1LL * nums[i - 1] * m - (s[i] - s[i - m]) <= k) {
return true;
}
}
return false;
};
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
};func maxFrequency(nums []int, k int) int {
n := len(nums)
sort.Ints(nums)
s := make([]int, n+1)
for i, x := range nums {
s[i+1] = s[i] + x
}
check := func(m int) bool {
for i := m; i <= n; i++ {
if nums[i-1]*m-(s[i]-s[i-m]) <= k {
return true
}
}
return false
}
l, r := 1, n
for l < r {
mid := (l + r + 1) >> 1
if check(mid) {
l = mid
} else {
r = mid - 1
}
}
return l
}function maxFrequency(nums: number[], k: number): number {
const n = nums.length;
nums.sort((a, b) => a - b);
const s: number[] = Array(n + 1).fill(0);
for (let i = 1; i <= n; ++i) {
s[i] = s[i - 1] + nums[i - 1];
}
let [l, r] = [1, n];
const check = (m: number): boolean => {
for (let i = m; i <= n; ++i) {
if (nums[i - 1] * m - (s[i] - s[i - m]) <= k) {
return true;
}
}
return false;
};
while (l < r) {
const mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}We can also use two pointers to maintain a sliding window, where all elements in the window can be changed to the maximum value in the window. The number of operations for the elements in the window is
Initially, we set the left pointer
The time complexity is
class Solution:
def maxFrequency(self, nums: List[int], k: int) -> int:
nums.sort()
ans = 1
s = j = 0
for i in range(1, len(nums)):
s += (nums[i] - nums[i - 1]) * (i - j)
while s > k:
s -= nums[i] - nums[j]
j += 1
ans = max(ans, i - j + 1)
return ansclass Solution {
public int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
int ans = 1;
long s = 0;
for (int i = 1, j = 0; i < nums.length; ++i) {
s += 1L * (nums[i] - nums[i - 1]) * (i - j);
while (s > k) {
s -= nums[i] - nums[j++];
}
ans = Math.max(ans, i - j + 1);
}
return ans;
}
}class Solution {
public:
int maxFrequency(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int ans = 1;
long long s = 0;
for (int i = 1, j = 0; i < nums.size(); ++i) {
s += 1LL * (nums[i] - nums[i - 1]) * (i - j);
while (s > k) {
s -= nums[i] - nums[j++];
}
ans = max(ans, i - j + 1);
}
return ans;
}
};func maxFrequency(nums []int, k int) int {
sort.Ints(nums)
ans := 1
s := 0
for i, j := 1, 0; i < len(nums); i++ {
s += (nums[i] - nums[i-1]) * (i - j)
for ; s > k; j++ {
s -= nums[i] - nums[j]
}
ans = max(ans, i-j+1)
}
return ans
}function maxFrequency(nums: number[], k: number): number {
nums.sort((a, b) => a - b);
let ans = 1;
let [s, j] = [0, 0];
for (let i = 1; i < nums.length; ++i) {
s += (nums[i] - nums[i - 1]) * (i - j);
while (s > k) {
s -= nums[i] - nums[j++];
}
ans = Math.max(ans, i - j + 1);
}
return ans;
}