Leetcode -1838- The frequency of the highest frequency element

Today move came late, already finished writing, has been running two sets of data + move, this data feel really not suitable for two

[Blog link]

The path to learning at šŸ”

The nuggets home page

[B].

The frequency of an element is the number of occurrences of that element in an array. I give you an integer array nums and an integer k. In a single operation, you can select a subscript of NUMs and increment the value of the corresponding element by 1. Returns the maximum possible frequency of the highest frequency element in the array after performing a maximum of k operations. Example 1: input: nums = [1,2,4], k = 5 output: 3 description: increment the first element three times and the second element two times, nums = [4,4,4]. Four is the highest frequency element in the array, frequency three. Example 2: input: nums = [1,4,8,13], k = 5 output: 2 explanation: there are several optimal solutions: - increment the first element three times, where nums = [4,4,8,13]. Four is the highest frequency element in the array, frequency two. - increment the second element four times, nums = [1,8,8,13]. Eight is the highest frequency element in the array, frequency two. - incrementing the third element five times, nums = [1,4,13,13]. 13 is the highest frequency element in the array, frequency 2. Example 3: Input: nums = [3,9,6], k = 2 Output: 1 Hint: 1 <= nums.length <= 105 1 <= nums[I] <= 105 1 <= k <= 105 Related Topics Array binary lookup prefix and sliding window šŸ‘ 64 šŸ‘Ž 0Copy the code

[ē­” ꔈ]

Leetcode topic link

[making address]

Code link

[introduction]

Prefix and + violent scan + sort

  • One way to think about it is whether we’re going to be operating on more than the largest element in the array
  • If we make the maximum element larger, and the maximum element is the most frequent element, then the rest of the operations increase accordingly
  • So we can assume that we don’t need to make the largest element * larger and that establishes a binary range
  • The sum of elements of the first element and the sum of elements of all elements
  • Let’s look at it with brute force. Don’t go through the whole thing
  • By comparing the prefix and +k to the element value * the number of elements,
  • Res said the current element sum [I] + k > = sum [I – res – 1) + (res + 1) * nums [I – 1)
  • If it does, take the number of elements * and increment res until res= I and return res
public int maxFrequency(int[] nums, int k) { Arrays.sort(nums); int n = nums.length; int res = 1; int[] sums = new int[n + 1]; sums[1] = nums[0]; for (int i = 2; i <= n; i++) { sums[i] = sums[i - 1] + nums[i - 1]; } // int I = 1; i <= n; While (RES < sums[I] + K >= sums[i-res-1] + (res +1) * nums[i-1]) {res++; } } return res; }Copy the code

Time complexity O(n2)O(n^{2})O(n2)

**n indicates the array length

Idea 2: Idea 1 + 2

  • In fact, idea one already mentioned the dichotomy but did not implement
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 code

Time complexity O(nāˆ— LGN)O(n*lg_{n})O(nāˆ— LGN)

However, I found that dichotomy was easier to TLE and felt that the median should be computed more in this data set