“This article has participated in the call for good writing activities, click to view: the back end, the big front end double track submission, 20,000 yuan prize pool waiting for you to challenge”

I am Chen PI, an ITer of Internet Coding. I search “Chen PI’s JavaLib” on wechat and read the latest articles as soon as possible, reply to [information], and then I can get the technical materials, electronic books, interview materials of first-line big factories and excellent resume templates carefully arranged by me.

The title

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
  • 3 increments for the first element and 2 increments for the second element, with 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 multiple optimal solutions:
    • Incrementing the first element three times, nums = [4,4,8,13]. Four is the highest frequency element in the array, frequency two.
    • Incrementing 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.

prompt

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105
  • 1 <= k <= 105

LeetCode


Analysis of the

The simplest solution is to use the brute force method, sort the original array first, then traverse each element in the array, the element before it, in the case of the number of operations does not exceed K, the frequency is increased by one, until the number of operations exceeds K. Time is O(n^2).

package com.chenpi;

import java.util.Arrays;

/ * * *@Description
 * @AuthorDried tangerine or orange peel *@Date 2021/7/19
 * @Version1.0 * /
public class MaxFrequency {

    public int maxFrequency(int[] nums, int k) {
        // Sort from smallest to largest
        Arrays.sort(nums);
        // Record the maximum frequency during the sliding process
        int max = 0;
        // Iterate over each element from left back (small to large) to determine if it is the element with the highest frequency
        for (int j = 0; j < nums.length; j++) {
            int i = j;
            int tempK = k;
            while (i >= 0 && ((nums[j] - nums[i]) <= tempK)) {
                tempK -= nums[j] - nums[i];
                i--;
            }
            max = Math.max(max, j - i);
        }
        return max;
    }

    public static void main(String[] args) {
        MaxFrequency maxFrequency = new MaxFrequency();
        int[] nums = {1.2.4};
        System.out.println(maxFrequency.maxFrequency(nums, 5)); }}Copy the code


However, the above solution is time-consuming when the array length is large. First sort the array from smallest to largest, then iterate over each element of the array, see the maximum length of the left window, that is, the frequency of the element, and then figure out the maximum number of these frequencies.

package com.chenpi;

import java.util.Arrays;

/ * * *@Description
 * @AuthorDried tangerine or orange peel *@Date 2021/7/19
 * @Version1.0 * /
public class MaxFrequency {

    public int maxFrequency(int[] nums, int k) {
        // Sort from smallest to largest
        Arrays.sort(nums);
        // Record the maximum frequency during the sliding process
        int max = 0;
        int tempSum = 0;
        // Iterate over each element from left back (small to large) to determine if it is the element with the highest frequency
        for (int i = 0, j = 0; j < nums.length; j++) {
            // j-i is the number of sliding window elements (excluding the last element nums) [j].
            // nums[j] * (j-i) -tempsum
            // If the difference is greater than k, it is not satisfied. The left window needs to slide back one bit and subtract the value of the callout window element
            while (nums[j] * (j - i) - tempSum > k) {
                tempSum -= nums[i++];
            }
            // Slide the right window back one bit and add the window value to the current element
            tempSum += nums[j];
            // What is the maximum frequency of the previous window or the current window
            max = Math.max(max, j - i + 1);
        }
        return max;
    }

    public static void main(String[] args) {
        MaxFrequency maxFrequency = new MaxFrequency();
        int[] nums = {1.4.8.13};
        System.out.println(maxFrequency.maxFrequency(nums, 5)); }}Copy the code


Previous problem and next problem

Previous question: LeetCode’s question of the Day “Roman numerals to integers”

Next question: Stay tuned