面试算法41：滑动窗口的平均值

2024-06-06 14:22| 来源: 网络整理| 查看: 265

题目

请实现如下类型MovingAverage，计算滑动窗口中所有数字的平均值，该类型构造函数的参数确定滑动窗口的大小，每次调用成员函数next时都会在滑动窗口中添加一个整数，并返回滑动窗口中所有数字的平均值。

public class MovingAverage { private Queue nums; private int capacity; }

例如，假设滑动窗口的大小为3。第1次调用next函数时在滑动窗口中添加整数1，此时窗口中只有一个数字1，因此返回平均值1。第2次调用next函数时添加整数2，此时窗口中有两个数字1和2，因此返回平均值1.5。第3次调用next函数时添加数字3，此时有3个数字1、2、3，因此返回平均值2。第4次调用next函数时添加数字4，由于受到窗口大小的限制，滑动窗口中最多只能有3个数字，因此第1个数字1将滑出窗口，此时窗口中包含3个数字2、3、4，返回平均值3。

分析

为了解决这个问题，首先需要考虑的是用什么数据结构来表示这个滑动窗口。按照题目的描述，可以在窗口中添加数字，当窗口中数字的数目超过限制时，还可以从窗口中删除数字。例如，当窗口的大小为3，在添加第4个数字时就需要从窗口中删除一个数字。需要注意的是，题目给出的例子中的删除规则是把最早添加进来的数字删除，因此这是一种“先入先出”的顺序，由此想到应该采用队列这种数据结构来表示滑动窗口。可以把数字添加到队列的尾部，并从队列的头部删除数字。

解 public class MovingAverage { private Queue nums; private int capacity; private int sum; public static void main(String[] args) { MovingAverage movingAverage = new MovingAverage(3); int[] array = {1, 2, 3, 4, 5, 6, 7}; for (int item : array) { double result = movingAverage.next(item); System.out.println(result); } } public MovingAverage(int size) { nums = new LinkedList(); capacity = size; } public double next(int val) { nums.offer(val); sum += val; if (nums.size() > capacity) { sum -= nums.poll(); } return (double)sum / nums.size(); } }

【本文地址】

公司简介

联系我们