Java O(1) solution, use Array as Sliding windows, runtime is 132ms, beat 99.73%


  • 0
    C

    The idea is to use an array int[] arr = new int[size] to keep the previous elements, use an int to keep the count of the inserting elements and a double to keep the sum. If a new element is waiting to insert:
    if count < arr.size

    1. put the new in the array
    2. sum = sum + new val;
    3. count ++
      $) cal the average
      else if count >= arr.length
    4. replace index = count % arr.length
    5. sum -= arr[replace index];
    6. arr[replace index] = new val
    7. sum += new val;
    8. avg = sum / arr.length;

    Code is attached below:

    public class MovingAverage {
    
        private int[] arr;
        int count;
        double sum;
    
        public MovingAverage(int size) {
            arr = new int[size];
            count = 0;
            sum = 0.0;
        }
        
        public double next(int val) {
            
            double avg = 0.0;
            int size = arr.length;
            if (size == 0)
                return avg;
            
            if (count < size) {
                arr[count] = val;
                sum += arr[count];
                count += 1;
                avg = sum / count;
            }
            else {
                int replace = count % size;
                sum -= arr[replace];
                arr[replace] = val;
                sum += val;
                count += 1;
                avg = sum / size;
            }
            return avg;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.