萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

力扣剑指Offer II 041-滑动窗口的平均值

发表于 2022-08-19 | 分类于 力扣刷题 | 0 | 阅读次数 56

题目描述

给定一个整数数据流和一个窗口大小,根据该滑动窗口的大小,计算滑动窗口里所有数字的平均值。

实现 MovingAverage 类:
MovingAverage(int size) 用窗口大小 size 初始化对象。
double next(int val) 成员函数 next 每次调用的时候都会往滑动窗口增加一个整数,请计算并返回数据流中最后 size 个值的移动平均值,即滑动窗口里所有数字的平均值。
题目链接

样例

输入:
inputs = ["MovingAverage", "next", "next", "next", "next"]
inputs = [[3], [1], [10], [3], [5]]

输出: [null, 1.0, 5.5, 4.66667, 6.0]

解释:
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // 返回 1.0 = 1 / 1
movingAverage.next(10); // 返回 5.5 = (1 + 10) / 2
movingAverage.next(3); // 返回 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // 返回 6.0 = (10 + 3 + 5) / 3

题目评估

官方难度:简单
知识点:队列、数组

分析

首先想到的是队列实现,使用数组创建一个size大小的队列,创建一个队列指针指向数组下标,标记队尾的下一位。记录当前队列数字的和,队列满了需要删除队首数字时让和减去队首数字。

Java代码题解

class MovingAverage {
    // 队列中数字和
    private double sum = 0L;
    // 队列最大长度
    private int size = 0;
    // 队列长度
    private int count = 0;
    // 队尾指针,指向队尾的下一位
    private int index = 0;
    // 队列
    private int[] queue;

    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        this.size = size;
        queue = new int[size];
    }
    
    public double next(int val) {
        double res;
        // 队列不满计数器加1
        if (count < size) {
            count++;
        }
        // 减去队头的值
        sum -= queue[index];
        // 队列入新值
        queue[index] = val;
        // 总数增加
        sum += val;
        // 计算平均值
        res = sum / count;
        // 队尾指针循环移动
        index = (index + 1) % size;
        return res;
    }
}

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */

复杂度分析

时间复杂度:O(1)
空间复杂度:O(size)

# 算法 # 程序设计 # 力扣
Redis常用指令
力扣剑指Offer 19-正则表达式匹配
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

77 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持