Encuentre 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).

Java

// java program code of Naive approach to
// find subarray with minimum average
import java.util.*;
 
class GFG {
 
    static void findsubarrayleast(int arr[], int k, int n)
    {
        int min = Integer.MAX_VALUE;
        int minindex = 0;
        for (int i = 0; i <= n - k; i++) {
            int sum = 0;
            for (int j = i; j < i + k; j++) {
                sum += arr[j];
            }
            if (sum < min) {
                min = sum;
                minindex = i;
            }
        }
        // printing the desired subarray
        System.out.println(
            "subarray with minimum average is: ");
        for (int i = minindex; i < minindex + k; i++) {
            System.out.print(arr[i] + " ");
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Test Case 1
        int arr[] = {20, 3, 13, 5, 10, 14, 8, 5, 11, 9, 1, 11};
        int n = arr.length;
        int k = 9;
 
        // function call
        findsubarrayleast(arr, k, n);
    }
}
 
// This code is contributed by Aarti_Rathi

C++

//C++ code of Naive approach to
//find subarray with minimum average
 
#include<bits/stdc++.h>
using namespace std;
//function to find subarray
void findsubarrayleast(int arr[],int k,int n){
    int min=INT_MAX,minindex;
    for (int i = 0; i <= n-k; i++)
    {
        int sum=0;
        for (int j = i; j < i+k; j++)
        {
            sum+=arr[j];
        }
        if(sum<min){
            min=sum;
            minindex=i;
        }
         
    }
  //printing the desired subarray
    cout<<"subarray with minimum average is: ";
    for (int i = minindex; i < minindex+k; i++)
    {
        cout<<arr[i]<<" ";
    }
    
     
}
//driver code
int main() {
int arr[]={3, 7, 90, 20, 10, 50, 40};
int n=sizeof(arr)/sizeof(arr[0]),k=3;
//function call
findsubarrayleast(arr,k,n);
return 0;
}
 
//this code is contributed by Machhaliya Muhammad

Python3

# Python3 program to find
# minimum average subarray
 
# Prints beginning and ending
# indexes of subarray of size k
# with minimum average
def findsubarrayleast(arr, k, n):
    min = 999999
    minindex = 0
    for i in range(n-k+1):
        sum = 0
        j = i
        for j in range(i, i+k):
            sum += arr[j]
        if sum < min:
            min = sum
            minindex = i
 
    # printing the desired subarray
    print("subarray with minimum average is: ", end='')
    for i in range(minindex, minindex+k):
        print(arr[i], end=" ")
 
 
# Driver Code
arr = [20, 3, 13, 5, 10, 14, 8, 5, 11, 9, 1, 11]
k = 9  # Subarray size
n = len(arr)
findsubarrayleast(arr, k, n)
 
# This code is contributed by Aarti_Rathi

C#

// C# program code of Naive approach to
//find subarray with minimum average
using System;
 
class GFG {
 
  static void findsubarrayleast(int []arr,int k,int n){
    int min = Int32.MaxValue;
    int minindex = 0;
    for (int i = 0; i <= n-k; i++)
    {
      int sum = 0;
      for (int j = i; j < i+k; j++)
      {
        sum += arr[j];
      }
      if(sum < min){
        min = sum;
        minindex = i;
      }
 
    }
    //printing the desired subarray
    Console.Write("subarray with minimum average is: ");
    for (int i = minindex; i < minindex+k; i++)
    {
      Console.Write(arr[i]+" ");
    }
 
 
  }
 
  // Driver Code
  static public void Main()
  {
    // Test Case 1
    int[] arr = { 3, 7, 90, 20, 10, 50, 40};
    int n = arr.Length;
    int k=3;
 
    // function call
    findsubarrayleast(arr,k,n);
  }
}
 
// This code is contributed by Aarti_Rathi

Javascript

// javascript program code of Naive approach to
// find subarray with minimum average
 
function findsubarrayleast(arr, k, n)
{
    var min = Number.MAX_VALUE;
    var minindex = 0;
    for (var i = 0; i < n - k; i++)
    {
        var sum = 0;
        for (var j=i; j < i + k; j++)
        {
            sum += arr[j];
        }
        if (sum < min)
        {
            min = sum;
            minindex = i;
        }
    }
    // printing the desired subarray
    console.log("subarray with minimum average is: ");
    for (var i=minindex; i < minindex + k; i++)
    {
        console.log(arr[i] + " ");
    }
}
     
// Driver Code
var arr = [3, 7, 90, 20, 10, 50, 40];
var n = arr.length;
var k = 3;
 
// function call
findsubarrayleast(arr, k, n);
 
// This code is contributed by Aarti_Rathi
Producción

subarray with minimum average is: 20 10 50 

Complejidad de tiempo: O(n*k) donde n es el tamaño de la array.
Espacio Auxiliar: O(1)

Una Solución Eficiente es resolver el problema anterior en O(n) tiempo y O(1) espacio adicional. 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. 

C++

// A Simple C++ program to find minimum average subarray
#include <bits/stdc++.h>
using namespace std;
 
// Prints beginning and ending indexes of subarray
// of size k with minimum average
void findMinAvgSubarray(int arr[], 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);
        }
    }
 
    cout << "Subarray between [" << res_index << ", "
         << res_index + k - 1 << "] has minimum average";
}
 
// Driver program
int main()
{
    int arr[] = { 3, 7, 90, 20, 10, 50, 40 };
    int k = 3; // Subarray size
    int n = sizeof arr / sizeof arr[0];
    findMinAvgSubarray(arr, n, k);
    return 0;
}

Java

// 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);
    }
}

Python3

# Python3 program to find
# minimum average subarray
 
# Prints beginning and ending
# indexes of subarray of size k
# with minimum average
def findMinAvgSubarray(arr, n, k):
 
    # k must be smaller than or equal to n
    if (n < k): return 0
 
    # Initialize beginning index of result
    res_index = 0
 
    # Compute sum of first subarray of size k
    curr_sum = 0
    for i in range(k):
        curr_sum += arr[i]
 
    # Initialize minimum sum as current sum
    min_sum = curr_sum
 
    # Traverse from (k + 1)'th
    # element to n'th element
    for i in range(k, n):
     
        # 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)
         
    print("Subarray between [", res_index,
          ", ", (res_index + k - 1),
          "] has minimum average")
 
# Driver Code
arr = [3, 7, 90, 20, 10, 50, 40]
k = 3 # Subarray size
n = len(arr)
findMinAvgSubarray(arr, n, k)
 
# This code is contributed by Anant Agarwal.

C#

// A Simple C# program to find
// minimum average subarray
using System;
 
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);
            }
        }
 
        Console.Write("Subarray between [" + res_index + ", " +
                     (res_index + k - 1) +
                     "] has minimum average");
    }
 
    // Driver method to test the above function
    public static void Main()
    {
        int k = 3; // Subarray size
        findMinAvgSubarray(arr.Length, k);
    }
}
 
// This code is contributed by nitin mittal.

PHP

<?php
// A Simple PHP program to find
// minimum average subarray
 
// Prints beginning and ending
// indexes of subarray of size
// k with minimum average
function findMinAvgSubarray($arr, $n, $k)
{
     
    // k must be smaller
    // than or equal to n
    if ($n < $k)
        return;
 
    // Initialize beginning
    // index of result
    $res_index = 0;
 
    // Compute sum of first
    // subarray of size k
    $curr_sum = 0;
    for ($i = 0; $i < $k; $i++)
        $curr_sum += $arr[$i];
 
    // Initialize minimum sum
    // as current sum
    $min_sum = $curr_sum;
 
    // Traverse from (k+1)'th element
    // to n'th element
    for ( $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);
        }
    }
 
    echo "Subarray between [" ,$res_index
          , ", " ,$res_index + $k - 1, "] has minimum average";
}
 
    // Driver Code
    $arr = array(3, 7, 90, 20, 10, 50, 40);
     
    // Subarray size
    $k = 3;
    $n = sizeof ($arr) / sizeof ($arr[0]);
    findMinAvgSubarray($arr, $n, $k);
    return 0;
 
// This code is contributed by nitin mittal.
?>

Javascript

<script>
 
// A Simple JavaScript program to find
// minimum average subarray
 
// Prints beginning and ending indexes
// of subarray of size k with minimum average
function findMinAvgSubarray(arr, n, k)
{
     
    // k must be smaller than or equal to n
    if (n < k)
        return;
 
    // Initialize beginning index of result
    let res_index = 0;
 
    // Compute sum of first subarray of size k
    let curr_sum = 0;
    for(let i = 0; i < k; i++)
        curr_sum += arr[i];
 
    // Initialize minimum sum as current sum
    let min_sum = curr_sum;
 
    // Traverse from (k+1)'th element
    // to n'th element
    for(let 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);
        }
    }
    document.write("Subarray between [" + res_index +
                   ", " + (res_index + k - 1) +
                   "] has minimum average");
}
 
// Driver code
let arr = [ 3, 7, 90, 20, 10, 50, 40 ];
 
// Subarray size
let k = 3;
let n = arr.length;
 
findMinAvgSubarray(arr, n, k);
 
// This code is contributed by Surbhi Tyagi.
 
</script>
Producción

Subarray between [3, 5] has minimum average

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

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *