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