Dada una array arr[] que contiene N enteros positivos y un entero K. La tarea es reemplazar cada elemento de la array con el promedio de los K elementos anteriores y los K siguientes . Además, si los elementos K no están presentes, ajuste el uso del número máximo de elementos disponibles antes y después.
Ejemplos:
Entrada: arr[] = {9, 7, 3, 9, 1, 8, 11}, K=2
Salida: 5 7 6 4 7 7 4
Explicación: Para i = 0, promedio = (7 + 3)/2 = 5
Para i = 1, promedio = (9 + 3 + 9)/3 = 7
Para i = 2, promedio = (9 + 7 + 9 + 1)/4 = 6
Para i = 3, promedio = (7 + 3 + 1 + 8)/4 = 4
Para i = 4, promedio = (3 + 9 + 8 + 11)/4 = 7
Para i = 5, promedio = (9 + 1 + 11)/3 = 7
Para i = 6, promedio = (1 + 8)/2 = 4Entrada: arr[] = {13, 26, 35, 41, 23, 18, 38}, K=3
Salida: 34 28 24 25 31 34 27
Enfoque ingenuo: el enfoque más simple es usar bucles anidados. El bucle exterior atravesará la array de izquierda a derecha, es decir, de i = 0 a i < N y un bucle interior atravesará la subarreglo desde el índice i – K hasta el índice i + K excepto i y calculará el promedio de ellos.
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 replace all array elements
// with the average of previous and
// next K elements
void findAverage(int arr[], int N, int K)
{
int start, end;
for (int i = 0; i < N; i++) {
int sum = 0;
// Start limit is max(i-K, 0)
start = max(i - K, 0);
// End limit in min(i+K, N-1)
end = min(i + K, N - 1);
int cnt = end - start;
for (int j = start; j <= end; j++) {
// Skipping the current element
if (j == i) {
continue;
}
sum += arr[j];
}
cout << sum / cnt << ' ';
}
}
// Driver Code
int main()
{
int arr[] = { 9, 7, 3, 9, 1, 8, 11 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 2;
findAverage(arr, N, K);
return 0;
}
Java
// Java program to implement
// the above approach
class GFG {
// Function to replace all array elements
// with the average of previous and
// next K elements
static void findAverage(int[] arr, int N, int K)
{
int start, end;
for (int i = 0; i < N; i++) {
int sum = 0;
// Start limit is max(i-K, 0)
start = Math.max(i - K, 0);
// End limit in min(i+K, N-1)
end = Math.min(i + K, N - 1);
int cnt = end - start;
for (int j = start; j <= end; j++) {
// Skipping the current element
if (j == i) {
continue;
}
sum += arr[j];
}
System.out.print(sum / cnt + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 9, 7, 3, 9, 1, 8, 11 };
int N = arr.length;
int K = 2;
findAverage(arr, N, K);
}
}
// This code is contributed by ukasp.
Python3
# Python code for the above approach # Function to replace all array elements # with the average of previous and # next K elements def findAverage(arr, N, K): start = None end = None for i in range(N): sum = 0 # Start limit is max(i-K, 0) start = max(i - K, 0) # End limit in min(i+K, N-1) end = min(i + K, N - 1) cnt = end - start for j in range(start, end + 1): # Skipping the current element if j == i: continue sum += arr[j] print((sum // cnt), end= " ") # Driver Code arr = [9, 7, 3, 9, 1, 8, 11] N = len(arr) K = 2 findAverage(arr, N, K) # This code is contributed by gfgking
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to replace all array elements
// with the average of previous and
// next K elements
static void findAverage(int []arr, int N, int K)
{
int start, end;
for (int i = 0; i < N; i++) {
int sum = 0;
// Start limit is max(i-K, 0)
start = Math.Max(i - K, 0);
// End limit in min(i+K, N-1)
end = Math.Min(i + K, N - 1);
int cnt = end - start;
for (int j = start; j <= end; j++) {
// Skipping the current element
if (j == i) {
continue;
}
sum += arr[j];
}
Console.Write(sum / cnt + " ");
}
}
// Driver Code
public static void Main()
{
int []arr = { 9, 7, 3, 9, 1, 8, 11 };
int N = arr.Length;
int K = 2;
findAverage(arr, N, K);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to replace all array elements
// with the average of previous and
// next K elements
function findAverage(arr, N, K)
{
let start, end;
for (let i = 0; i < N; i++)
{
let sum = 0;
// Start limit is max(i-K, 0)
start = Math.max(i - K, 0);
// End limit in min(i+K, N-1)
end = Math.min(i + K, N - 1);
let cnt = end - start;
for (let j = start; j <= end; j++) {
// Skipping the current element
if (j == i) {
continue;
}
sum += arr[j];
}
document.write(Math.floor(sum / cnt) + ' ');
}
}
// Driver Code
let arr = [9, 7, 3, 9, 1, 8, 11];
let N = arr.length;
let K = 2;
findAverage(arr, N, K);
// This code is contributed by Potta Lokesh
</script>
Producción
5 7 6 4 7 7 4
Complejidad temporal: O(N 2 )
Espacio auxiliar: O(1)
Enfoque eficiente: este enfoque utiliza el método de ventana deslizante . Siga los pasos que se mencionan a continuación para implementar este concepto:
- Considere que cada elemento tiene K elementos anteriores y siguientes y tome una ventana de tamaño 2*K + 1 para cubrir todo este rango.
- Ahora encuentre inicialmente la suma de los primeros (K+1) elementos.
- Mientras recorre la array:
- Calcule el promedio dividiendo la suma con (tamaño de la ventana-1).
- Agregue el siguiente elemento después del extremo derecho de la ventana actual.
- Elimina el elemento más a la izquierda de la ventana actual. Esto moverá la ventana una posición a la derecha
- Imprime la array resultante.
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 replace all array elements
// with the average of previous and
// next K elements
void findAverage(int arr[], int N, int K)
{
int i, sum = 0, next, prev, update;
int cnt = 0;
// Calculate initial sum of K+1 elements
for (i = 0; i <= K and i < N; i++) {
sum += arr[i];
cnt += 1;
}
// Using the sliding window technique
for (i = 0; i < N; i++) {
update = sum - arr[i];
cout << update / (cnt - 1) << " ";
next = i + K + 1;
prev = i - K;
if (next < N) {
sum += arr[next];
cnt += 1;
}
if (prev >= 0) {
sum -= arr[prev];
cnt-=1;
}
}
}
// Driver Code
int main()
{
int arr[] = { 9, 7, 3, 9, 1, 8, 11 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 2;
findAverage(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class GFG
{
// Function to replace all array elements
// with the average of previous and
// next K elements
static void findAverage(int arr[], int N, int K)
{
int i, sum = 0, next = 0, prev = 0, update = 0;
int cnt = 0;
// Calculate initial sum of K+1 elements
for (i = 0; i <= K && i < N; i++) {
sum += arr[i];
cnt += 1;
}
// Using the sliding window technique
for (i = 0; i < N; i++) {
update = sum - arr[i];
System.out.print(update / (cnt - 1) + " ");
next = i + K + 1;
prev = i - K;
if (next < N) {
sum += arr[next];
cnt += 1;
}
if (prev >= 0) {
sum -= arr[prev];
cnt-=1;
}
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 9, 7, 3, 9, 1, 8, 11 };
int N = arr.length;
int K = 2;
findAverage(arr, N, K);
}
}
// This code is contributed by Samim Hossain Mondal
Python3
# Python program for the above approach # Function to replace all array elements # with the average of previous and # next K elements def findAverage(arr, N, K): sum = 0; next = 0; prev = 0; update = 0; cnt = 0; # Calculate initial sum of K+1 elements for i in range(0, K + 1, 1): if(i >= N): break sum += arr[i]; cnt += 1; # Using the sliding window technique for i in range(0, N): update = sum - arr[i]; print(update // (cnt - 1), end=" "); next = i + K + 1; prev = i - K; if (next < N): sum += arr[next]; cnt += 1; if (prev >= 0): sum -= arr[prev]; cnt -= 1; # Driver Code if __name__ == '__main__': arr = [9, 7, 3, 9, 1, 8, 11]; N = len(arr); K = 2; findAverage(arr, N, K); # This code is contributed by 29AjayKumar
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to replace all array elements
// with the average of previous and
// next K elements
static void findAverage(int []arr, int N, int K)
{
int i, sum = 0, next = 0, prev = 0, update = 0;
int cnt = 0;
// Calculate initial sum of K+1 elements
for (i = 0; i <= K && i < N; i++) {
sum += arr[i];
cnt += 1;
}
// Using the sliding window technique
for (i = 0; i < N; i++) {
update = sum - arr[i];
Console.Write(update / (cnt - 1) + " ");
next = i + K + 1;
prev = i - K;
if (next < N) {
sum += arr[next];
cnt += 1;
}
if (prev >= 0) {
sum -= arr[prev];
cnt-=1;
}
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 9, 7, 3, 9, 1, 8, 11 };
int N = arr.Length;
int K = 2;
findAverage(arr, N, K);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for the above approach
// Function to replace all array elements
// with the average of previous and
// next K elements
const findAverage = (arr, N, K) => {
let i, sum = 0, next, prev, update;
let cnt = 0;
// Calculate initial sum of K+1 elements
for (i = 0; i <= K && i < N; i++) {
sum += arr[i];
cnt += 1;
}
// Using the sliding window technique
for (i = 0; i < N; i++) {
update = sum - arr[i];
document.write(`${parseInt(update / (cnt - 1))} `);
next = i + K + 1;
prev = i - K;
if (next < N) {
sum += arr[next];
cnt += 1;
}
if (prev >= 0) {
sum -= arr[prev];
cnt -= 1;
}
}
}
// Driver Code
let arr = [9, 7, 3, 9, 1, 8, 11];
let N = arr.length;
let K = 2;
findAverage(arr, N, K);
// This code is contributed by rakeshsahni
</script>
Producción
5 7 6 4 7 7 4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por pintusaini y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA