大厂面试真题详解:数据流滑动窗口平均值-阿里云开发者社区

开发者社区> 算法编程> 正文

大厂面试真题详解:数据流滑动窗口平均值

简介: 大厂面试真题详解:数据流滑动窗口平均值

给出一串整数流和窗口大小,计算滑动窗口中所有整数的平均值。

在线评测地址:领扣题库官网

样例1 :

MovingAverage m = new MovingAverage(3);
m.next(1) = 1 // 返回 1.00000
m.next(10) = (1 + 10) / 2 // 返回 5.50000
m.next(3) = (1 + 10 + 3) / 3 // 返回 4.66667
m.next(5) = (10 + 3 + 5) / 3 // 返回 6.00000

解题思路

我们需要一个数据结构来维护在窗口中的值,这个数据结构有一个要求,当存储的数个数大于窗口大小m时,需要弹出最先进入的数,这正好时队列的性质,所以可以用队列来维护。

算法:队列模拟滑动窗口

  1. 初始化时新建一个队列。
  2. 每次调用next(x)时,将x加入队列1。
  3. 如果队列长度大于m,弹出队首。
  4. 计算结果并返回。

复杂度分析

设窗口大小为m。
时间复杂度

  • 单次next()时间复杂度O(1)
  • 队列插入和弹出都是O(1)。
    空间复杂度
  • 最多存储m个数,空间复杂度为O(m)。
public class MovingAverage {

    private Queue<Integer> queue;
    private double sum = 0;
    private int size;

    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        queue = new LinkedList<Integer>();
        this.size = size;
    }
    
    public double next(int val) {
        sum += val;
        if (queue.size() == size) {
            sum = sum - queue.poll();
        }
        queue.offer(val);
        return sum / queue.size();
    }
}

更多题解参考:九章官网solution

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接