Máximo de elementos que se pueden igualar con k actualizaciones | conjunto 2

elementos máximos que se pueden igualar con un máximo de k actualizaciones/incrementos.

Ejemplos:

Entrada :
Salida :

Entrada :
Salida :
Explicación:
Entrada :
Salida :

Enfoque: Este es un enfoque de espacio optimizado del enfoque eficiente discutido en el Conjunto 1 del artículo .

La tarea se puede resolver con la ayuda del concepto de ventana deslizante . Básicamente, para cada ventana desde (i hasta j), vemos si todos los elementos de la ventana actual se pueden igualar al último elemento de la ventana . Si es posible en la mayoría de las k actualizaciones, almacene el tamaño de la ventana, de lo contrario, descarte el elemento inicial de la ventana.

Siga los pasos a continuación para resolver el problema:

• Ordenar los números de array .
• Declare una suma variable entera para almacenar la suma acumulada de los elementos de la array.
• Declare una variable entera y almacene la frecuencia máxima posible del elemento más frecuente en la array nums .
• Sea i…j la ventana actual que estamos procesando.
• Atraviesa la array nums.
• Básicamente, en cada paso, estamos tratando de hacer que todos los elementos de nums[i] a nums[j] sean iguales a nums[j].
• Si la suma de todos los elementos de nums[i] a nums[j] más el valor de k es suficiente para hacerlo, entonces la ventana es válida.
• De lo contrario, el valor de i debe incrementarse porque la diferencia de valores de nums[i] y nums[j] es máxima, por lo que nums[i] toma la parte máxima de k para volverse igual a nums[j] , por eso debe eliminarse de la ventana actual.
• El valor de ans es igual al tamaño de la ventana válida actual, es decir (ji)
• Imprime la frecuencia del elemento más frecuente en array nums.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum count of
// equal elements
void getMax(vector<int>& nums, int k)
{
    // Size of nums array
    int n = nums.size();
 
    // Sort the nums array
    sort(nums.begin(), nums.end());
 
    // Stores the running sum
    // of array elements
    long sum = 0;
 
    // Stores the maximum possible frequency
    int ans = 0;
 
    // i is the starting index of the window
    // j is the ending index of the window
    int i, j;
    i = j = 0;
 
    // Traverse the array nums
    for (j = 0; j < n; j++) {
 
        // Add the value of
        // current element to sum
        sum += nums[j];
 
        // If the addition of sum
        // and k is sufficient to
        // make all the array elements
        // from i..j equal to nums[j]
        if ((long)(sum + k)
            >= ((long)nums[j] * (j - i + 1)))
            continue;
 
        // Update the value of ans
        // to store the maximum
        // possible frequency so far
        if ((j - i) > ans)
            ans = j - i;
 
        // Subtract the value of nums[i] from sum,
        // because the addition of sum and
        // k are not sufficient to make
        // all the array elements from i..j
        // equal to nums[j] and difference of
        // values of A[j] and A[i] is maximum,
        // so A[i] takes the maximum part of k
        // to become equal to A[j],
        // that's why it is removed
        // from current window.
        sum -= nums[i];
 
        // Slide the current window
        i++;
    }
 
    // Update the value of ans if required
    ans = max(ans, j - i);
 
    // Print the result
    cout << ans << endl;
}
 
// Driver Code
int main()
{
    vector<int> nums = { 1, 3, 4 };
    int k = 6;
    getMax(nums, k);
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG
{
 
  // Function to find the maximum count of
  // equal elements
  static void getMax(int nums[ ], int k)
  {
 
    // Size of nums array
    int n = nums.length;
 
    // Sort the nums array
    Arrays.sort(nums);
 
    // Stores the running sum
    // of array elements
    long sum = 0;
 
    // Stores the maximum possible frequency
    int ans = 0;
 
    // i is the starting index of the window
    // j is the ending index of the window
    int i, j;
    i = j = 0;
 
    // Traverse the array nums
    for (j = 0; j < n; j++) {
 
      // Add the value of
      // current element to sum
      sum += nums[j];
 
      // If the addition of sum
      // and k is sufficient to
      // make all the array elements
      // from i..j equal to nums[j]
      if ((long)(sum + k)
          >= ((long)nums[j] * (j - i + 1)))
        continue;
 
      // Update the value of ans
      // to store the maximum
      // possible frequency so far
      if ((j - i) > ans)
        ans = j - i;
 
      // Subtract the value of nums[i] from sum,
      // because the addition of sum and
      // k are not sufficient to make
      // all the array elements from i..j
      // equal to nums[j] and difference of
      // values of A[j] and A[i] is maximum,
      // so A[i] takes the maximum part of k
      // to become equal to A[j],
      // that's why it is removed
      // from current window.
      sum -= nums[i];
 
      // Slide the current window
      i++;
    }
 
    // Update the value of ans if required
    ans = Math.max(ans, j - i);
 
    // Print the result
    System.out.println(ans);
 
  }
  public static void main (String[] args)
  {
    int nums[ ] = { 1, 3, 4 };
    int k = 6;
    getMax(nums, k);
  }
}
 
// This code is contributed by hrithikgarg03188

# Python program for the above approach
 
# Function to find the maximum count of
# equal elements
def getMax(nums, k):
     
    # Size of nums array
    n = len(nums)
 
    # Sort the nums array
    nums.sort()
 
    # Stores the running sum
    # of array elements
    sum = 0
 
    # Stores the maximum possible frequency
    ans = 0
 
    # i is the starting index of the window
    # j is the ending index of the window
    i = j = f = 0
     
    # Traverse the array nums
    for j in range(n):
     
        # Add the value of
        # current element to sum
        sum = sum + nums[j]
 
        # If the addition of sum
        # and k is sufficient to
        # make all the array elements
        # from i..j equal to nums[j]
        if ((sum + k) >= (nums[j] * (j - i + 1))):
            f = 1
            continue
 
        # Update the value of ans
        # to store the maximum
        # possible frequency so far
        if ((j - i) > ans):
            ans = j - i
 
        # Subtract the value of nums[i] from sum,
        # because the addition of sum and
        # k are not sufficient to make
        # all the array elements from i..j
        # equal to nums[j] and difference of
        # values of A[j] and A[i] is maximum,
        # so A[i] takes the maximum part of k
        # to become equal to A[j],
        # that's why it is removed
        # from current window.
        sum = sum - nums[i]
 
        # Slide the current window
        i = i + 1
         
        f = 1
 
    # Update the value of ans if required
    if(f == 1):
        ans = max(ans, j - i + 1)
    else:
        ans = max(ans, j - i)
 
    # Print the result
    print(ans)
 
# Driver Code
nums = [ 1, 3, 4 ]
k = 6
getMax(nums, k)
 
# This code is contributed by Samim Hossain Mondal.

// C# program for the above approach
using System;
 
class GFG
{
 
    // Function to find the maximum count of
    // equal elements
    static void getMax(int[] nums, int k)
    {
 
        // Size of nums array
        int n = nums.Length;
 
        // Sort the nums array
        Array.Sort(nums);
 
        // Stores the running sum
        // of array elements
        long sum = 0;
 
        // Stores the maximum possible frequency
        int ans = 0;
 
        // i is the starting index of the window
        // j is the ending index of the window
        int i, j;
        i = j = 0;
 
        // Traverse the array nums
        for (j = 0; j < n; j++)
        {
 
            // Add the value of
            // current element to sum
            sum += nums[j];
 
            // If the addition of sum
            // and k is sufficient to
            // make all the array elements
            // from i..j equal to nums[j]
            if ((long)(sum + k)
                >= ((long)nums[j] * (j - i + 1)))
                continue;
 
            // Update the value of ans
            // to store the maximum
            // possible frequency so far
            if ((j - i) > ans)
                ans = j - i;
 
            // Subtract the value of nums[i] from sum,
            // because the addition of sum and
            // k are not sufficient to make
            // all the array elements from i..j
            // equal to nums[j] and difference of
            // values of A[j] and A[i] is maximum,
            // so A[i] takes the maximum part of k
            // to become equal to A[j],
            // that's why it is removed
            // from current window.
            sum -= nums[i];
 
            // Slide the current window
            i++;
        }
 
        // Update the value of ans if required
        ans = Math.Max(ans, j - i);
 
        // Print the result
        Console.Write(ans);
 
    }
    public static void Main()
    {
        int[] nums = { 1, 3, 4 };
        int k = 6;
        getMax(nums, k);
    }
}
 
// This code is contributed by Saurabh Jaiswal

<script>
       // JavaScript code for the above approach
 
       // Function to find the maximum count of
       // equal elements
       function getMax(nums, k)
       {
        
           // Size of nums array
           let n = nums.length;
 
           // Sort the nums array
           nums.sort(function (a, b) { return a - b })
 
           // Stores the running sum
           // of array elements
           let sum = 0;
 
           // Stores the maximum possible frequency
           let ans = 0;
 
           // i is the starting index of the window
           // j is the ending index of the window
           let i, j;
           i = j = 0;
 
           // Traverse the array nums
           for (j = 0; j < n; j++) {
 
               // Add the value of
               // current element to sum
               sum += nums[j];
 
               // If the addition of sum
               // and k is sufficient to
               // make all the array elements
               // from i..j equal to nums[j]
               if ((sum + k)
                   >= (nums[j] * (j - i + 1)))
                   continue;
 
               // Update the value of ans
               // to store the maximum
               // possible frequency so far
               if ((j - i) > ans)
                   ans = j - i;
 
               // Subtract the value of nums[i] from sum,
               // because the addition of sum and
               // k are not sufficient to make
               // all the array elements from i..j
               // equal to nums[j] and difference of
               // values of A[j] and A[i] is maximum,
               // so A[i] takes the maximum part of k
               // to become equal to A[j],
               // that's why it is removed
               // from current window.
               sum -= nums[i];
 
               // Slide the current window
               i++;
           }
 
           // Update the value of ans if required
           ans = Math.max(ans, j - i);
 
           // Print the result
           document.write(ans + '<br>')
       }
 
       // Driver Code
       let nums = [1, 3, 4];
       let k = 6;
       getMax(nums, k);
        
 // This code is contributed by Potta Lokesh
   </script>

3

Complejidad de tiempo: O(N*log(N)), donde N es el tamaño de la array nums
Espacio auxiliar: O(1)