Dado un arreglo arr[] de tamaño N y un entero K, la tarea es imprimir la diferencia entre el promedio máximo y mínimo de los subarreglos contiguos de longitud K.
Ejemplos:
Entrada: arr[ ] = {3, 8, 9, 15}, K = 2
Salida: 6.5
Explicación:
Todos los subarreglos de longitud 2 son {3, 8}, {8, 9}, {9, 15} y sus promedios son (3+8)/2 = 5,5, (8+9)/2 = 8,5 y (9+15)/2 = 12,0 respectivamente.
Por lo tanto, la diferencia entre el máximo (= 12,0) y el mínimo (= 5,5) es 12,0 -5,5 = 6,5.Entrada: arr[] = {17, 6.2, 19, 3.4}, K = 3
Salida: 4.533
Enfoque ingenuo: el enfoque más simple es encontrar el promedio de cada subarreglo contiguo de tamaño K y luego encontrar el máximo y el mínimo de estos valores e imprimir su diferencia.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the difference between
// averages of the maximum and the minimum
// subarrays of length k
double Avgdifference(double arr[], int N, int K)
{
// Stores min and max sum
double min = 1000000, max = -1;
// Iterate through starting points
for (int i = 0; i <= N - K; i++) {
double sum = 0;
// Sum up next K elements
for (int j = 0; j < K; j++) {
sum += arr[i + j];
}
// Update max and min moving sum
if (min > sum)
min = sum;
if (max < sum)
max = sum;
}
// Return the difference between max
// and min average
return (max - min) / K;
}
// Driver Code
int main()
{
// Given Input
double arr[] = { 3, 8, 9, 15 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 2;
// Function Call
cout << Avgdifference(arr, N, K);
return 0;
}
Java
// Java implementation of the above approach
import java.io.*;
class GFG
{
// Function to find the difference between
// averages of the maximum and the minimum
// subarrays of length k
static double Avgdifference(double arr[], int N, int K)
{
// Stores min and max sum
double min = 1000000, max = -1;
// Iterate through starting points
for (int i = 0; i <= N - K; i++) {
double sum = 0;
// Sum up next K elements
for (int j = 0; j < K; j++) {
sum += arr[i + j];
}
// Update max and min moving sum
if (min > sum)
min = sum;
if (max < sum)
max = sum;
}
// Return the difference between max
// and min average
return (max - min) / K;
}
// Driver Code
public static void main (String[] args)
{
// Given Input
double arr[] = { 3, 8, 9, 15 };
int N =arr.length;
int K = 2;
// Function Call
System.out.println( Avgdifference(arr, N, K));
}
}
// This code is contributed by Potta Lokesh
Python3
# Python program for the above approach # Function to find the difference between # averages of the maximum and the minimum # subarrays of length k def Avgdifference(arr, N, K): # Stores min and max sum min = 1000000; max = -1; # Iterate through starting points for i in range(N - K + 1): sum = 0; # Sum up next K elements for j in range(K): sum += arr[i + j]; # Update max and min moving sum if (min > sum): min = sum; if (max < sum): max = sum; # Return the difference between max # and min average return (max - min) / K; # Driver Code # Given Input arr = [3, 8, 9, 15]; N = len(arr); K = 2; # Function Call print(Avgdifference(arr, N, K)); # This code is contributed by _saurabh_jaiswal.
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the difference between
// averages of the maximum and the minimum
// subarrays of length k
static double Avgdifference(double []arr, int N, int K)
{
// Stores min and max sum
double min = 1000000, max = -1;
// Iterate through starting points
for(int i = 0; i <= N - K; i++)
{
double sum = 0;
// Sum up next K elements
for(int j = 0; j < K; j++)
{
sum += arr[i + j];
}
// Update max and min moving sum
if (min > sum)
min = sum;
if (max < sum)
max = sum;
}
// Return the difference between max
// and min average
return(max - min) / K;
}
// Driver Code
public static void Main (String[] args)
{
// Given Input
double []arr = { 3, 8, 9, 15 };
int N = arr.Length;
int K = 2;
// Function Call
Console.Write(Avgdifference(arr, N, K));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript program for the above approach
// Function to find the difference between
// averages of the maximum and the minimum
// subarrays of length k
function Avgdifference(arr, N, K) {
// Stores min and max sum
let min = 1000000, max = -1;
// Iterate through starting points
for (let i = 0; i <= N - K; i++) {
let sum = 0;
// Sum up next K elements
for (let j = 0; j < K; j++) {
sum += arr[i + j];
}
// Update max and min moving sum
if (min > sum)
min = sum;
if (max < sum)
max = sum;
}
// Return the difference between max
// and min average
return (max - min) / K;
}
// Driver Code
// Given Input
let arr = [3, 8, 9, 15];
let N = arr.length;
let K = 2;
// Function Call
document.write(Avgdifference(arr, N, K));
</script>
Producción
6.5
Complejidad temporal: O(N*K)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando la técnica de la ventana deslizante . Siga los pasos a continuación para resolver el problema:
- Encuentre la suma de los subarreglos en el rango [0, K-1] y guárdelo en una variable, digamos sum .
- Inicialice dos variables, digamos max y min , para almacenar la suma máxima y mínima de cualquier subarreglo de tamaño K.
- Iterar sobre el rango [K, N-K+1] usando la variable i y realizar los siguientes pasos:
- Elimine el elemento arr[iK] y agregue el elemento arr[i] a las ventanas de tamaño K. Es decir, actualice sum a sum+arr[i]-arr[iK].
- Actualice min como el mínimo de min y sum, y actualice max como el máximo de max y sum .
- Finalmente, después de completar los pasos anteriores, imprima la respuesta como (max-min)/K.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the difference between
// the maximum and minimum subarrays of
// length K
double Avgdifference(double arr[], int N, int K)
{
// Stores the sum of subarray over the
// range [0, K]
double sum = 0;
// Iterate over the range [0, K]
for (int i = 0; i < K; i++)
sum += arr[i];
// Store min and max sum
double min = sum;
double max = sum;
// Iterate over the range [K, N-K]
for (int i = K; i <= N - K + 1; i++) {
// Increment sum by arr[i]-arr[i-K]
sum += arr[i] - arr[i - K];
// Update max and min moving sum
if (min > sum)
min = sum;
if (max < sum)
max = sum;
}
// Return difference between max and min
// average
return (max - min) / K;
}
// Driver Code
int main()
{
// Given Input
double arr[] = { 3, 8, 9, 15 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 2;
// Function Call
cout << Avgdifference(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to find the difference between
// the maximum and minimum subarrays of
// length K
static double Avgdifference(double arr[], int N, int K)
{
// Stores the sum of subarray over the
// range [0, K]
double sum = 0;
// Iterate over the range [0, K]
for(int i = 0; i < K; i++)
sum += arr[i];
// Store min and max sum
double min = sum;
double max = sum;
// Iterate over the range [K, N-K]
for(int i = K; i <= N - K + 1; i++)
{
// Increment sum by arr[i]-arr[i-K]
sum += arr[i] - arr[i - K];
// Update max and min moving sum
if (min > sum)
min = sum;
if (max < sum)
max = sum;
}
// Return difference between max and min
// average
return(max - min) / K;
}
// Driver Code
public static void main (String[] args)
{
// Given Input
double arr[] = { 3, 8, 9, 15 };
int N = arr.length;
int K = 2;
// Function Call
System.out.println(Avgdifference(arr, N, K));
}
}
// This code is contributed by shivanisinghss2110
Python3
# python 3 program for the above approach # Function to find the difference between # the maximum and minimum subarrays of # length K def Avgdifference(arr, N, K): # Stores the sum of subarray over the # range [0, K] sum = 0 # Iterate over the range [0, K] for i in range(K): sum += arr[i] # Store min and max sum min = sum max = sum # Iterate over the range [K, N-K] for i in range(K,N - K + 2,1): # Increment sum by arr[i]-arr[i-K] sum += arr[i] - arr[i - K] # Update max and min moving sum if (min > sum): min = sum if (max < sum): max = sum # Return difference between max and min # average return (max - min) / K # Driver Code if __name__ == '__main__': # Given Input arr = [3, 8, 9, 15] N = len(arr) K = 2 # Function Call print(Avgdifference(arr, N, K)) # This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the difference between
// the maximum and minimum subarrays of
// length K
static double Avgdifference(double []arr, int N, int K)
{
// Stores the sum of subarray over the
// range [0, K]
double sum = 0;
// Iterate over the range [0, K]
for(int i = 0; i < K; i++)
sum += arr[i];
// Store min and max sum
double min = sum;
double max = sum;
// Iterate over the range [K, N-K]
for(int i = K; i <= N - K + 1; i++)
{
// Increment sum by arr[i]-arr[i-K]
sum += arr[i] - arr[i - K];
// Update max and min moving sum
if (min > sum)
min = sum;
if (max < sum)
max = sum;
}
// Return difference between max and min
// average
return(max - min) / K;
}
// Driver Code
public static void Main (String[] args)
{
// Given Input
double []arr = { 3, 8, 9, 15 };
int N = arr.Length;
int K = 2;
// Function Call
Console.Write(Avgdifference(arr, N, K));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript program for the above approach
// Function to find the difference between
// the maximum and minimum subarrays of
// length K
function Avgdifference(arr, N, K)
{
// Stores the sum of subarray over the
// range [0, K]
let sum = 0;
// Iterate over the range [0, K]
for(let i = 0; i < K; i++)
sum += arr[i];
// Store min and max sum
let min = sum;
let max = sum;
// Iterate over the range [K, N-K]
for(let i = K; i <= N - K + 1; i++)
{
// Increment sum by arr[i]-arr[i-K]
sum += arr[i] - arr[i - K];
// Update max and min moving sum
if (min > sum)
min = sum;
if (max < sum)
max = sum;
}
// Return difference between max and min
// average
return(max - min) / K;
}
// Driver Code
// Given Input
let arr = [ 3, 8, 9, 15 ];
let N = arr.length;
let K = 2;
// Function Call
document.write(Avgdifference(arr, N, K));
// This code is contributed by shivanisinghss2110
</script>
Producción
6.5
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohitpal210 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA