GuilinDev
Lc1838
05 August 2008
1838 Frequency of the Most Frequent Element
array经历k次增加操作，potentially出现最多次数的数字的频率
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxFrequency(int[] A, int k) {
int res = 1, i = 0, j;
long sum = 0;
Arrays.sort(A);
for (j = 0; j < A.length; ++j) {
sum += A[j];
while (sum + k < (long)A[j] * (j - i + 1)) {
sum -= A[i];
i += 1;
}
res = Math.max(res, j - i + 1);
}
return res;
}
Sort and then maintain a sliding window.
1
2
3
4
Sort and traverse the array starting from the 2nd element;
For each upper bound of the sliding window, compute how many operations needed to make all the elements within the sliding window equal, and deduct it from k;
If k is not big enough to finish the operations, increase lower bound and change k accordingly.
After all iterations, the windown width is the solution.
1
2
3
4
5
6
7
8
9
10
11
12
public int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
int lo = 0, hi = 1; // lower and upper bounds of the sliding window.
while (hi < nums.length) {
k -= (nums[hi] - nums[hi - 1]) * (hi - lo); // deduct the # of operations needed make all elements in the window equal.
if (k < 0) {
k += nums[hi] - nums[lo++];
}
++hi;
}
return hi - lo;
}