Golang | Leetcode Golang题解之第480题滑动窗口中位数

题目:

题解:

type hp struct {
    sort.IntSlice
    size int
}
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{}   { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }
func (h *hp) push(v int)         { h.size++; heap.Push(h, v) }
func (h *hp) pop() int           { h.size--; return heap.Pop(h).(int) }
func (h *hp) prune() {
    for h.Len() > 0 {
        num := h.IntSlice[0]
        if h == small {
            num = -num
        }
        if d, has := delayed[num]; has {
            if d > 1 {
                delayed[num]--
            } else {
                delete(delayed, num)
            }
            heap.Pop(h)
        } else {
            break
        }
    }
}

var delayed map[int]int
var small, large *hp

func medianSlidingWindow(nums []int, k int) []float64 {
    delayed = map[int]int{} // 哈希表,记录「延迟删除」的元素,key 为元素,value 为需要删除的次数
    small = &hp{}           // 大根堆,维护较小的一半元素
    large = &hp{}           // 小根堆,维护较大的一半元素
    makeBalance := func() {
        // 调整 small 和 large 中的元素个数,使得二者的元素个数满足要求
        if small.size > large.size+1 { // small 比 large 元素多 2 个
            large.push(-small.pop())
            small.prune() // small 堆顶元素被移除,需要进行 prune
        } else if small.size < large.size { // large 比 small 元素多 1 个
            small.push(-large.pop())
            large.prune() // large 堆顶元素被移除,需要进行 prune
        }
    }
    insert := func(num int) {
        if small.Len() == 0 || num <= -small.IntSlice[0] {
            small.push(-num)
        } else {
            large.push(num)
        }
        makeBalance()
    }
    erase := func(num int) {
        delayed[num]++
        if num <= -small.IntSlice[0] {
            small.size--
            if num == -small.IntSlice[0] {
                small.prune()
            }
        } else {
            large.size--
            if num == large.IntSlice[0] {
                large.prune()
            }
        }
        makeBalance()
    }
    getMedian := func() float64 {
        if k&1 > 0 {
            return float64(-small.IntSlice[0])
        }
        return float64(-small.IntSlice[0]+large.IntSlice[0]) / 2
    }

    for _, num := range nums[:k] {
        insert(num)
    }
    n := len(nums)
    ans := make([]float64, 1, n-k+1)
    ans[0] = getMedian()
    for i := k; i < n; i++ {
        insert(nums[i])
        erase(nums[i-k])
        ans = append(ans, getMedian())
    }
    return ans
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/897123.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

SCCB协议与IIC协议不同

SCCB开始信号与结束信号都与IIC协议的大概一致&#xff0c;这里就不细讲了 开始、结束信号参考&#xff1a;【I2C】IIC读写时序_iic读时序-CSDN博客 SSCB写时序&#xff1a; 即&#xff1a;start phase_1 phase_2 phase_3 stop SCCB读时序&#xff1a; 即&#xff…

电脑视频剪辑大比拼,谁更胜一筹?

随着短视频的火爆&#xff0c;越来越多的人开始尝试自己动手制作视频&#xff0c;无论是记录生活点滴还是创作个性短片&#xff0c;一款好用的视频剪辑软件是必不可少的。今天&#xff0c;我们就从短视频运营的角度&#xff0c;来聊聊几款热门的电脑视频剪辑软件&#xff0c;看…

在做题中学习(66):两数相加

解法&#xff1a;模拟 思路&#xff1a;定义一个变量t&#xff0c;存储相加后的结果&#xff0c;个位赋给新节点&#xff0c;十位&#xff08;表示有进位&#xff09;留下&#xff0c;累加到下一次加法&#xff08;相当于上进位&#xff09;。while里即便cur1和cur2都为空了&a…

windows文件拷贝给wsl2的Ubuntu

参考&#xff1a; windows文件如何直接拖拽到wsl中_win 移到文件到wsl-CSDN博客 cp -r /mnt/盘名/目标文件 要复制到wsl中的位置e.g.cp -r /mnt/d/byt5 /home Linux文件复制、移动、删除等操作命令_linux移动命令-CSDN博客 Linux 文件、文件夹的复制、移动、删除 - Be-myse…

重生之“我打数据结构,真的假的?”--1.顺序表(无习题)

C语言中的顺序表详细总结 1. 概述 顺序表&#xff08;Sequential List&#xff09;是一种线性数据结构&#xff0c;用于存储具有相同数据类型的一组元素。顺序表采用一段连续的存储空间&#xff0c;使用数组来实现&#xff0c;能够高效地支持随机访问操作。在 C 语言中&#…

No.19 笔记 | WEB安全 - 任意文件操作详解 part 1

1. 任意文件上传漏洞基础 什么是文件上传功能? 在网站和应用中,我们经常会看到允许用户上传文件的功能,比如: 更换头像:让用户上传自己的照片作为头像发布图片:在社交媒体或论坛上传图片提交文档:在办公系统中上传Word、Excel等文档 这些都是常见的文件上传功能。 任意文…

RabbitMQ系列学习笔记(四)--消息应答机制

文章目录 一、消息应答详解1、基本概念2、自动应答3、手动应答4、自动重新入队5、手动应答代码6、手动应答演示 二、不公平分发三、预取值机制 本文参考&#xff1a; 尚硅谷RabbitMQ教程丨快速掌握MQ消息中间件rabbitmq RabbitMQ 详解 Centos7环境安装Erlang、RabbitMQ详细过程…

如何去掉歌曲的人声只剩伴奏?伴奏独享的方法

在音乐制作、后期处理或是个人娱乐中&#xff0c;我们经常遇到需要将歌曲中的人声去除&#xff0c;仅保留伴奏的情况。虽然这一过程可能听起来颇为复杂&#xff0c;但实际上&#xff0c;借助现代音乐技术和软件&#xff0c;我们可以较为轻松地达成这一目标。本文将介绍三种常见…

[AWS]RDS数据库版本升级

背景&#xff1a;由于AWS上mysql5.7版本不再支持&#xff0c;需要进行版本升级。 吐槽&#xff1a;每年都要来那么几次&#xff0c;真的有病一样&#xff0c;很烦。 步骤一、升级检查 AWS提供了一个python的升级检测脚本&#xff0c;可以按照一下脚本下载测试&#xff1a; [r…

机器视觉基础系列2—简单了解用神经网络进行深度估计

机器视觉基础系列2—简单了解深度估计 深度估计 深度估计通俗的来讲就是要得到一张图像当中&#xff0c;哪些区域离得比较近&#xff0c;哪些区域离得比较远。 输入一张彩色得图像&#xff0c;我们输出深度估计得图像&#xff0c;深浅即为远近&#xff08;从而完成了离相机距离…

Git安装与配置(2.47.0版本超详细)

一、背景 1.什么是gitt&#xff1f;&#xff08;官网引用&#xff09; Git 是一个快速、可扩展的分布式版本控制系统&#xff0c;它拥有异常丰富的命令集&#xff0c;可以提供高级操作和对内部的完全访问。 参阅 gittutorial[7] 开始使用&#xff0c;然后查看 giteveryday[7] …

【2022统考真题】计算时间复杂度

目录 一、题目描述 二、思路分析 三、易错提醒 四、同级和嵌套的关系 一、题目描述 下列程序段的时间复杂度是&#xff08;&#xff09; int sum 0; for (int i 1; i < n; i * 2) for (int j 0; j < i; j) sum; A. O(logn) B. O(n) C. O(nlogn) D…

使用Radzen Blazor组件库开发的基于ABP框架炫酷UI主题

一、项目简介 使用过ABP框架的童鞋应该知道它也自带了一款免费的Blazor UI主题&#xff0c;它的页面是长这样的&#xff1a; 个人感觉不太美观&#xff0c;于是网上搜了很多Blazor开源组件库&#xff0c;发现有一款样式非常不错的组件库&#xff0c;名叫&#xff1a;Radzen&am…

iEnglish「速成」板块上线,快速提升英语能力

10月17日&#xff0c;iEnglish智能升级版正式推出了「速成」板块&#xff0c;这一创新举措不仅是AI教育深度融合的体现&#xff0c;还为用户提供了更为高效的个性化学习体验。 据悉&#xff0c;「速成」板块旨在通过个性化的学习模式和多元化的练习方式&#xff0c;帮助用户实…

SSD |(九)ECC原理 | LDPC

文章目录 &#x1f4da;信号和噪声&#x1f4da;通信系统模型&#x1f4da;纠错编码的基本思想&#x1f407;编码距离&#x1f407;线性纠错码的基石——奇偶校验&#x1f407;校验矩阵H和生成矩阵G &#x1f4da;LDPC原理简介&#x1f407;LDPC是什么&#x1f407;Tanner图 &a…

scrapy案例——当当网的爬取一

项目名称&#xff1a;当当网的爬取一——爬取青春文学的书籍数据 案例需求&#xff1a; 1.使用scrapy爬虫技术爬取当当网中青春文学的书籍数据&#xff0c;包括&#xff08;标题、现价、定价、作者、出版日期、出版社、书本详情和书本图片url&#xff09; 2.将获取到的数据保…

免费开源的微信开发框架

近年来&#xff0c;随着人工智能技术的快速发展&#xff0c;聊天机器人在各个领域得到了广泛的应用。在社交媒体中&#xff0c;自动回复成为了一个流行的功能&#xff0c;让用户可以方便地与机器人进行互动。gewe框架&#xff0c;一个开源的微信聊天机器人框架&#xff0c;实现…

高刚性重切削数控走心机

高刚性重切削数控走心机&#xff0c;作为现代精密加工领域的佼佼者&#xff0c;以其卓越的性能和广泛的应用领域&#xff0c;赢得了众多行业的青睐。下面&#xff0c;我将从多个方面为您详细解析这种数控走心机。 ‌一、定义与特点‌ ‌定义‌&#xff1a;高刚性重切削数控走心…

【Java 并发编程】单例模式

前言 单例模式是一种十分常用但却相对而言比较简单的单例模式。虽然它简单但是包含了关于线程安全、内存模型、类加载机制等一些比较核心的知识点。本章会介绍单例模式的设计思想&#xff0c;会去讲解了几种常见的单例实现方式&#xff0c;如饿汉式、懒汉式、双重检锁、静态内部…

C++和OpenGL实现3D游戏编程【连载16】——详解三维坐标转二维屏幕坐标(向量和矩阵操作实战)

&#x1f525;C和OpenGL实现3D游戏编程【目录】 1、本节课要实现的内容 在上一课我们了解了着色器&#xff0c;了解了部分核心模式编程内容&#xff0c;从中接触到了线性代数中向量和矩阵相关知识&#xff0c;我们已经能够感受到向量和矩阵在OpenGL编程中的重要性。特别是后期…