Programa Java para encontrar el subarreglo con el promedio mínimo

Dada una array arr[] de tamaño n y entero k tal que k <= n.

Ejemplos: 

Input:  arr[] = {3, 7, 90, 20, 10, 50, 40}, k = 3
Output: Subarray between indexes 3 and 5
The subarray {20, 10, 50} has the least average 
among all subarrays of size 3.

Input:  arr[] = {3, 7, 5, 20, -10, 0, 12}, k = 2
Output: Subarray between [4, 5] has minimum average

Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.

Una solución simple es considerar cada elemento como el comienzo de un subarreglo de tamaño k y calcular la suma del subarreglo que comienza con este elemento. La complejidad temporal de esta solución es O(nk).

Una Solución Eficiente es resolver el problema anterior en O(n) tiempo y O(1) espacio extra. La idea es utilizar una ventana corredera de tamaño k. Mantenga un registro de la suma de los k elementos actuales. Para calcular la suma de la ventana actual, elimine el primer elemento de la ventana anterior y agregue el elemento actual (último elemento de la ventana actual).

1) Initialize res_index = 0 // Beginning of result index
2) Find sum of first k elements. Let this sum be 'curr_sum'
3) Initialize min_sum = sum
4) Iterate from (k+1)'th to n'th element, do following
   for every element arr[i]
      a) curr_sum = curr_sum + arr[i] - arr[i-k]
      b) If curr_sum < min_sum
           res_index = (i-k+1)
5) Print res_index and res_index+k-1 as beginning and ending
   indexes of resultant subarray.

A continuación se muestra la implementación del algoritmo anterior. 

// A Simple Java program to find 
// minimum average subarray
  
class Test {
      
    static int arr[] = new int[] { 3, 7, 90, 20, 10, 50, 40 };
  
    // Prints beginning and ending indexes of subarray
    // of size k with minimum average
    static void findMinAvgSubarray(int n, int k)
    {
        // k must be smaller than or equal to n
        if (n < k)
            return;
  
        // Initialize beginning index of result
        int res_index = 0;
  
        // Compute sum of first subarray of size k
        int curr_sum = 0;
        for (int i = 0; i < k; i++)
            curr_sum += arr[i];
  
        // Initialize minimum sum as current sum
        int min_sum = curr_sum;
  
        // Traverse from (k+1)'th element to n'th element
        for (int i = k; i < n; i++) 
        {
            // Add current item and remove first
            // item of previous subarray
            curr_sum += arr[i] - arr[i - k];
  
            // Update result if needed
            if (curr_sum < min_sum) {
                min_sum = curr_sum;
                res_index = (i - k + 1);
            }
        }
  
        System.out.println("Subarray between [" +
                            res_index + ", " + (res_index + k - 1) +
                            "] has minimum average");
    }
  
    // Driver method to test the above function
    public static void main(String[] args)
    {
        int k = 3; // Subarray size
        findMinAvgSubarray(arr.length, k);
    }
}

Producción: 

Subarray between [3, 5] has minimum average

Complejidad temporal: O(n) 
Espacio auxiliar: O(1)

Consulte el artículo completo sobre Encuentre el subarreglo con el promedio mínimo para obtener más detalles.