Question

Given an array ? of numbers and a window size ?, the sliding window ending at index ? is the subarray ?[? − ? + 1],⋯,?[?] if ? ≥ ? − 1, and ?[0],⋯,?[?] otherwise. For example, if ? = [0,2,4,6,8] and ? = 3, then the sliding windows ending at indices 0, 1, 2, 3 and 4 are respectively [0], [0,2], [0,2,4], [2,4,6], and [4,6,8]. Write a method, movingAverage, that given as input an array ? of numbers and a window size ?, returns an array ? with the same length as ?, such that for every index ?, ?[?] is the average of the numbers in the sliding window ending at index ?. The skeleton for the method is provided in the file MovingAverage.java.

The following is a sample run.

Input: ? = [0,2,4,6,8], ? = 3 Return: [0,1,2,4,6] Explanation: As explained above, the sliding windows at indices 0, 1, 2, 3 and 4 are respectively [0], [0,2], [0,2,4], [2,4,6], and [4,6,8]. The average of the numbers in these sliding windows are respectively = 0, = 1, = 2, = 4, and = 6.

Your method must have time complexity ?(?), where ? is the length of the input array ?.

Hint: You may find a queue useful.

public class MovingAverage {

   /**
   * Given an array of integers and a window size, computes the average of the integers in
   * the sliding window ending at each index.
   *
   * Time Complexity: O(n), where n is the length of the input array
   *
   * @param A an array of integers
   * @param w a window size
   * @return an array of doubles with the same length as A, whose element at index i is the
   * average of the integers in the sliding window ending at index i in the input array A
   */
   public double[] movingAverage(int[] A, int w) {
      
       //Replace this line with your return statement
       return null;
   }

}

Answer 1

public double[] movingAverage(int[] A, int w) {

   int n=A.length;

    double[] Avg = new double[n];

     Avg[0]=A[0];

      int sum=A[0],j=1,k=0;

     for(int i=k;i<w;i++){

       j++;

        sum=sum+A[i];

        Avg[++k]=sum/j;

}

   sum=0;

   for(int i=1;i<=w;i++){

    sum=sum+A[i];    

   }

   Avg[++k]=sum/w;

   for(int i=w+1;j<n;j++){

     sum=sum+A[i]-A[i-w];

      Avg[++k]=sum/w;

   }

      
       //Replace this line with your return statement
       return Avg;
  }