This article is participating in Python Theme Month. See the link to the event for more details
Topic describes
This is the frequency of the 1838 highest frequency element in LeetCode, and the difficulty is medium.
Tag: Enumeration, hash table, sort, prefix and, dichotomy, sliding window, double pointer
The frequency of an element is the number of times that element appears in an array.
I give you an array of integers numsnumsnums and an integer KKK.
In one step, you can select a subscript of numsnumsnums and increase the value of the element corresponding to that subscript by 111.
After performing a maximum of KKK operations, returns the maximum possible frequency of the highest frequency element in the array.
Example 1:
Input: nums = [1,2,4], k = 5 output: 3 description: increments the first element three times, increments the second element two times, then nums = [4,4,4]. 4 is the highest frequency element in the array, and the frequency is 3.Copy the codeExample 2:
Input: nums = [1,4,8,13], k = 5 output: 2 description: there are multiple optimal solutions: - perform three increments on the first element, at which point nums = [4,4,8,13]. 4 is the highest frequency element in the array, and the frequency is 2. - increments the second element four times, where nums = [1,8,8,13]. 8 is the highest frequency element in the array, and the frequency is 2. - increments the third element five times, where nums = [1,4,13,13]. 13 is the highest frequency element in the array. The frequency is 2.Copy the codeExample 3:
Input: nums = [3,9,6], k = 2 output: 1Copy the codeTip:
- 1 <= nums.length <=
- 1 <= nums[i] <=
- 1 <= k <=
The enumeration
A simple way to do this is to sort the original array numsnumsnums and then enumerate what the final “frequency value” is.
Since each operation can only be added logarithmically, we can start from the “corresponding value of frequency” and check back, so as to get the maximum number of “corresponding value of frequency” with a certain value under the premise that the number of operations does not exceed KKK.
The overall complexity of the algorithm is O(n2)O(n^2)O(n2), Java 2021/07/19 can pass.
Java code:
class Solution {
public int maxFrequency(int[] nums, int k) {
int n = nums.length;
Map<Integer, Integer> map = new HashMap<>();
for (int i : nums) map.put(i, map.getOrDefault(i, 0) + 1);
List<Integer> list = new ArrayList<>(map.keySet());
Collections.sort(list);
int ans = 1;
for (int i = 0; i < list.size(); i++) {
int x = list.get(i), cnt = map.get(x);
if (i > 0) {
int p = k;
for (int j = i - 1; j >= 0; j--) {
int y = list.get(j);
int diff = x - y;
if (p >= diff) {
int add = p / diff;
int min = Math.min(map.get(y), add);
p -= min * diff;
cnt += min;
} else {
break;
}
}
}
ans = Math.max(ans, cnt);
}
returnans; }}Copy the codePython 3 code:
class Solution:
def maxFrequency(self, nums: List[int], k: int) - >int:
n = len(nums)
hashmap = defaultdict(int)
for i in nums:
hashmap[i] += 1
ans = 1
lt = sorted(hashmap.keys())
for i in range(len(lt)):
x = lt[i]
cnt = hashmap[lt[i]]
if i > 0:
p = k
for j in range(i - 1, -1, -1):
y = lt[j]
diff = x - y
if p >= diff:
add = p // diff
m = min(hashmap[y], add)
p -= m * diff
cnt += m
else:
break
ans = max(ans, cnt)
return ans
Copy the code- Time complexity: the selection complexity is O(n)O(n)O(n) O(n) after the frequency is obtained; In the worst case, there are still NNN frequencies after repetition, and the maximum complexity of a frequency in KKK operations is O(n)O(n)O(n). The overall complexity is O(n2)O(n^2)O(n2).
- Space complexity: O(n)O(n)O(n)
Sort + prefix and + dichotomy + sliding window
So let’s do the original array
Order from smallest to largest, if there is a real optimal solution
, means that there exists at least one of size
The range of
So that the number of operations does not exceed
Of the interval
The arbitrary value
Is adjusted to
.
This leads us to quickly determine whether a certain range [l,r][l, r][l,r] can be changed to nums[r]nums[r]nums[r] in KKK operations:
Specifically, we can binary the answer lenlenlen as the window length, using the prefix and we can sum any interval in the complexity of O(1)O(1)O(1) O(1), and since each operation can only add one logarithmically, all the numbers in the window will eventually become nums[r]nums[r]nums[r], The final sum of the target interval is NUMs [r]∗ Lennums [r] * lennums[r]∗len. By comparing the difference between the sum of the target interval and the sum of the true interval, we can know whether KKK operations can change the current interval to nums[r]nums[r]nums[r].
The complexity of the above check operation to determine whether a certain value lenlenlen is feasible is O(n)O(n)O(n) O(n), so the algorithm complexity is O(nlogn)O(n\log{n})O(nlogn).
Java code:
class Solution {
int[] nums, sum;
int n, k;
public int maxFrequency(int[] _nums, int _k) {
nums = _nums;
k = _k;
n = nums.length;
Arrays.sort(nums);
sum = new int[n + 1];
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
int l = 0, r = n;
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return r;
}
boolean check(int len) {
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
int cur = sum[r + 1] - sum[l];
int t = nums[r] * len;
if (t - cur <= k) return true;
}
return false; }}Copy the codePython 3 code:
class Solution:
def maxFrequency(self, nums: List[int], k: int) - >int:
def check(length) :
for i in range(n+1-length):
j = i + length - 1
cur = presum[j + 1] - presum[i]
t = nums[j] * length
if t - cur <= k:
return True
return False
n = len(nums)
nums.sort()
presum = [0] + list(accumulate(nums))
l, r = 0, n
while l < r:
mid = l + r + 1 >> 1
if check(mid):
l = mid
else:
r = mid - 1
return r
Copy the code- Time complexity: The sorting complexity is
; Calculate the prefix and array complexity as
;checkThe complexity of the function is
, so the dichotomous complexity is
. The overall complexity is
- Space complexity: O(n)O(n)O(n)
The last
This is article No.1838 in our “Brush through LeetCode” series, which began on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some with locks, and we will first brush through all the questions without locks.
In this series of articles, in addition to explaining how to solve the problem, I’ll give you the most concise code possible. If the general solution is involved, the corresponding code template will be provided.
In order to facilitate the students to debug and submit the code on the computer, I set up a related warehouse: github.com/SharingSour… .
In the repository address, you can see the solution to the series, the corresponding code to the series, the LeetCode link, and other preferred solutions to the series.