每日一题——插入排序实现数据流中的中位数
插入排序实现数据流中的中位数
- 题目描述
- 功能要求
- 数据范围
- 解题思路
- 算法流程
- 代码实现
- 代码详解
- 1. 全局变量
- 2. Insert 函数
- 3. GetMedian 函数
- 复杂度分析
- Insert 函数
- GetMedian 函数
- 空间复杂度(整体)
- 注意事项
题目描述
设计一个算法,用来计算数据流中的中位数。当数据流中读出奇数个数值时,中位数就是所有数值排序之后位于中间的数值;当数据流中读出偶数个数值时,中位数就是所有数值排序之后中间两个数的平均值。
功能要求
- Insert(num):从数据流中读取一个整数,并将其插入到有序数组中
- GetMedian():返回当前读取数据的中位数
数据范围
- 数组大小限制:1000
- 确保数据流中所有整数都在 int 范围内
解题思路
本题采用有序数组的方式实现,主要思路如下:
- 使用一个全局数组保存所有数据
- 每次插入时保持数组有序
- 根据数组长度的奇偶性计算中位数
算法流程
- 插入数据时,先将数据加入数组末尾
- 通过插入排序的方式维护数组有序性
- 获取中位数时,根据数组长度判断返回中间位置或中间两个数的平均值
代码实现
/*** 全局变量声明区*/
#include <math.h>// 定义一个固定大小的数组来存储数据流中的数字
int arr[1000];// 定义top指针,初始化为-1表示空数组
// top表示当前数组中最后一个元素的索引
int top = -1;/*** Insert函数:将新的数字插入到数组中,并保持数组有序* @param num: 要插入的新数字* @return: 无返回值* 算法思路:使用插入排序的思想,每次插入后保持数组有序*/
void Insert(int num) {// 先将新数字插入到数组末尾// ++top先自增再使用,所以先给top加1,再在新位置存入数字arr[++top] = num;// 使用插入排序的思想,将新插入的数字调整到正确的位置// i>0确保不会数组越界// arr[i]<arr[i-1]判断当前数字是否小于前一个数字for(int i = top; i > 0 && arr[i] < arr[i-1]; i--) {// 如果当前数字小于前一个数字,则交换它们的位置int temp = arr[i]; // 暂存当前数字arr[i] = arr[i-1]; // 将前一个数字后移arr[i-1] = temp; // 将当前数字放到前一个位置}// 打印当前插入的结果// top表示当前位置,arr[top]表示当前位置的数字printf("arr%d=%d", top, arr[top]);
}/*** GetMedian函数:计算当前数组中所有数字的中位数* @param: 无参数* @return: 返回中位数,double类型* 算法思路:根据数组长度的奇偶性来决定返回中间一个数还是中间两个数的平均值*/
double GetMedian() {// 通过判断top的奇偶性来确定数组长度的奇偶性// top是索引,所以实际长度是top+1if(top % 2 == 0) {// 如果top是偶数,说明数组长度是奇数// 直接返回中间位置的数字// 需要转换为double类型以确保精确度return (double)arr[top/2];} else {// 如果top是奇数,说明数组长度是偶数// 返回中间两个数字的平均值// 使用2.0来进行浮点数除法,确保结果的精确度return (arr[top/2] + arr[top/2+1]) / 2.0;}
}
代码详解
1. 全局变量
int arr[1000]; // 存储数据的数组
int top = -1; // 数组当前末尾索引
- arr:用于存储所有插入的数据
- top:记录当前数组最后一个元素的索引,初始为-1表示空数组
2. Insert 函数
void Insert(int num) {arr[++top] = num;for(int i = top; i > 0 && arr[i] < arr[i-1]; i--) {int temp = arr[i];arr[i] = arr[i-1];arr[i-1] = temp;}printf("arr%d=%d", top, arr[top]);
}
关键点解析:
- 先将新数据加入数组末尾
- 使用插入排序方法,将新插入的数据调整到正确位置
- 打印输出当前插入的数据及其位置
3. GetMedian 函数
double GetMedian() {if(top % 2 == 0)return (double)arr[top/2];elsereturn (arr[top/2] + arr[top/2+1]) / 2.0;
}
关键点解析:
- 通过判断top的奇偶性确定当前数组长度的奇偶性
- 奇数个元素时返回中间位置的元素
- 偶数个元素时返回中间两个数的平均值
- 使用2.0确保进行浮点数除法
复杂度分析
Insert 函数
- 时间复杂度:O(n),其中n为当前数组长度
- 空间复杂度:O(1),只需要常数级别的额外空间
GetMedian 函数
- 时间复杂度:O(1),直接访问数组元素
- 空间复杂度:O(1)
空间复杂度(整体)
- O(n),需要一个数组存储所有数据
注意事项
-
数组大小限制
- 需要确保不会超过1000个元素
- 实际应用中应考虑动态扩容
-
数值范围
- 确保输入的整数在int范围内
- 计算平均值时注意使用double避免精度损失
-
边界条件
- 处理第一个数据时的特殊情况
- 注意数组索引不要越界,基本上只要注意边界问题,插入排序整体上还是非常容易的
相关文章:
每日一题——插入排序实现数据流中的中位数
插入排序实现数据流中的中位数 题目描述功能要求数据范围 解题思路算法流程 代码实现代码详解1. 全局变量2. Insert 函数3. GetMedian 函数 复杂度分析Insert 函数GetMedian 函数空间复杂度(整体) 注意事项 题目描述 设计一个算法,用来计算数…...
arcgis for js范围内天地图高亮,其余底图灰暗
在GIS地图开发中,有时我们需要突出显示某个特定区域,而将其他区域灰暗处理,以达到视觉上的对比效果。本文将介绍如何使用ArcGIS for JavaScript实现这一功能,具体效果为:在指定范围内,天地图高亮显示&#…...
【Unity】从父对象中获取子对象组件的方式
1.GetComponentInChildren 用于获取对与指定组件或游戏对象的任何子级相同的游戏对象上的组件类型的引用。 该方法在Unity脚本API的声明格式为: public T GetComponentInChildren(bool includeInactive false) includeInactive参数(可选)…...
code run使用vs2015工具链构建
"cpp": "cmd.exe /C \"\"D:\\Microsoft Visual Studio 14.0\\VC\\vcvarsall.bat\" x86 && cl.exe $fileName /Fe:$fileNameWithoutExt.exe && $dir$fileNameWithoutExt.exe\"" 效果如下: // hello#includ…...
matlab快速入门(2)-- 数据处理与可视化
MATLAB的数据处理 1. 数据导入与导出 (1) 从文件读取数据 Excel 文件:data readtable(data.xlsx); % 读取为表格(Table)CSV 文件:data readtable(data.csv); % 自动处理表头和分隔符文本文件:data load(data.t…...
UnityShader学习笔记——动态效果
——内容源自唐老狮的shader课程 目录 1.原理 2.Shader中内置的时间变量 3.Shader中经常会改变的数据 4.纹理动画 4.1.背景滚动 4.1.1.补充知识 4.1.2.基本原理 4.2.帧动画 4.2.1.基本原理 5.流动的2D河流 5.1.基本原理 5.2.关键步骤 5.3.补充知识 6.广告牌效果 …...
Docker Desktop安装到其他盘
Docker Desktop 默认安装到c盘,占用空间太大了,想给安装到其他盘,网上找了半天的都不对 正确安装命令: start /w "" "Docker Desktop Installer.exe" install --installation-dirF:\docker命令执行成功&am…...
详细教程 | 如何使用DolphinScheduler调度Flink实时任务
Apache DolphinScheduler 非常适用于实时数据处理场景,尤其是与 Apache Flink 的集成。DolphinScheduler 提供了丰富的功能,包括任务依赖管理、动态调度、实时监控和日志管理,能够有效简化 Flink 实时任务的管理和部署。通过 DolphinSchedule…...
稻盛和夫如何描述能力
1. 能力的三要素 稻盛和夫认为,能力由以下三个核心要素组成: 知识(Knowledge):掌握的专业知识、技术技能和行业经验。 技能(Skill):将知识应用于实际工作的能力,包括解决…...
【LeetCode 刷题】贪心算法(4)-区间问题
此博客为《代码随想录》二叉树章节的学习笔记,主要内容为贪心算法区间问题的相关题目解析。 文章目录 55. 跳跃游戏45. 跳跃游戏 II452. 用最少数量的箭引爆气球435. 无重叠区间763. 划分字母区间56. 合并区间 55. 跳跃游戏 题目链接 class Solution:def canJump…...
javaEE初阶————多线程初阶(3)
大家新年快乐呀,今天是第三期啦,大家前几期的内容掌握的怎么样啦? 1,线程死锁 1.1 构成死锁的场景 a)一个线程一把锁 这个在java中是不会发生的,因为我们之前讲的可重入机制,在其他语言中可…...
Deep Sleep 96小时:一场没有硝烟的科技保卫战
2025年1月28日凌晨3点,当大多数人还沉浸在梦乡时,一场没有硝烟的战争悄然打响。代号“Deep Sleep”的服务器突遭海量数据洪流冲击,警报声响彻机房,一场针对中国关键信息基础设施的网络攻击来势汹汹! 面对美国发起的这场…...
【AI应用】免费的文本转语音工具:微软 Edge TTS 和 开源版 ChatTTS 对比
【AI论文解读】【AI知识点】【AI小项目】【AI战略思考】【AI日记】【读书与思考】【AI应用】 我试用了下Edge TTS,感觉还不错,不过它不支持克隆声音(比如自己的声音) 微软 Edge TTS 和 开源版 ChatTTS 都是免费的 文本转语音&…...
Deepseek-v3 / Dify api接入飞书机器人go程序
准备工作 开通了接收消息权限的飞书机器人,例如我希望用户跟飞书机器人私聊,就需要开通这个权限:读取用户发给机器人的单聊消息 im:message.p2p_msg:readonly准备好飞书机器人的API key 和Secretdeepseek-v3的api keysecret:http…...
流媒体技术原理
流媒体技术的原理主要涉及以下几个核心概念和技术: 1. 编码和压缩 编码:视频和音频原始数据通常非常庞大。为了传输和存储,首先需要通过编码将这些数据转换成更小、更易处理的格式。常见视频编码标准包括H.264、H.265(HEVC&…...
matlab simulink 三级倒立摆LQR控制
1、内容简介 略 matlab simulink 122-三级倒立摆LQR控制 可以交流、咨询、答疑 2、内容说明 略 要求初始条件[0.01 0.01 0.01 0.01 0 0 0 0] 调节时间希望在3s内,超调量尽量的小,最大不能超过0.05; 用simulink的…...
使用令牌桶算法通过redis实现限流
令牌桶算法是一种常用的限流算法,它可以平滑地控制请求的处理速率。在 Java 中结合 Redis 实现令牌桶算法,可以利用 Redis 的原子操作来保证多节点环境下的限流效果。 一 实现思路 初始化令牌桶:在 Redis 中存储令牌桶的相关信息࿰…...
Tableau实用技巧 —— 提取Tableau文件中图片
需求背景 在日常开发过程中,我们时常会遇到两种图片提取需求:一是本地报告中的图片文件丢失需要找回,二是从网络论坛中发现有价值的报告图片希望保存使用。针对这些实际应用场景,以下将详细介绍有效的图片提取方法。 解决思路 …...
记一次golang环境的变化
前两天编译打包了了个文件,把env的 goos 搞坏了 导致运行项目一直报错 先是这样 go: unsupported GOOS/GOARCH pair windows/amd64再是这样 /amd64supported GOOS/GOARCH pair linux咱就说,咱也是知道环境配置的有问题 ( go env GOOS &…...
web直播弹幕抓取分析 signature
声明: 本文章中所有内容仅供学习交流使用,不用于其他任何目的,抓包内容、敏感网址、数据接口等均已做脱敏处理,严禁用于商业用途和非法用途,否则由此产生的一切后果均与作者无关! 前言 最近遇到太多难点了卡了很久&am…...
CVE-2024-13025-Codezips 大学管理系统 faculty.php sql 注入分析及拓展
Codezips 里面有很多cms系统,其中的一个College Management System In PHP With Source Code存在sql注入漏洞。 复现 对源码进行下载登录。 里面有很多远程js加载不出来但是不影响接口使用。 对于/college-mgmt-php-master/Front-end/faculty.php接口进行测试。…...
第二个Qt开发实例:在Qt中利用GPIO子系统和sysfs伪文件系统实现按钮(Push Button)点击控制GPIO口(效果为LED2灯的灭和亮)
引言 本文承接博文 https://blog.csdn.net/wenhao_ir/article/details/145420998 里的代码,在那里面代码的基础上添加上利用sysfs伪文件系统实现按钮(Push Button)点击控制GPIO口的代码,进而实现LED2灯的灭和亮。 最终的效果是点击下面的LED按钮实现LED…...
【自动化测试】使用Python selenium类库模拟手人工操作网页
使用Python selenium类库模拟手人工操作网页 背景准备工作安装Python版本安装selenium类库下载selenium驱动配置本地环境变量 自动化脚本输出页面表单自动化填充相关代码 背景 待操作网页必须使用IE浏览器登录访问用户本地只有edge浏览器,通过edge浏览器IE模式访问…...
Elasticsearch:向量搜索的快速介绍
作者:来自 Elastic Valentin Crettaz 本文是三篇系列文章中的第一篇,将深入探讨向量搜索(也称为语义搜索)的复杂性,以及它在 Elasticsearch 中的实现方式。 本文是三篇系列文章中的第一篇,将深入探讨向量搜…...
低至3折,百度智能云千帆宣布全面支持DeepSeek-R1/V3调用
DeepSeek-R1和 DeepSeek-V3模型已在百度智能云千帆平台上架 。 出品|产业家 新年伊始,百度智能云又传来新动作 。 2月3日百度智能云宣布, DeepSeek-R1和 DeepSeek-V3模型已在百度智能云千帆平台上架,同步推出超低价格方案,并…...
VSCode中使用EmmyLua插件对Unity的tolua断点调试
一.VSCode中搜索安装EmmyLua插件 二.创建和编辑launch.json文件 初始的launch.json是这样的 手动编辑加上一段内容如下图所示: 三.启动调试模式,并选择附加的进程...
RabbitMQ 从入门到精通:从工作模式到集群部署实战(三)
文章目录 使用CLI管理RabbitMQrabbitmqctlrabbitmq-queuesrabbitmq-diagnosticsrabbitmq-pluginsrabbitmq-streamsrabbitmq-upgraderabbitmqadmin 使用CLI管理RabbitMQ RabbitMQ CLI 工具需要安装兼容的 Erlang/OTP版本。 这些工具假定系统区域设置为 UTF-8(例如en…...
2025软件授权与保护领域的新趋势
2024年对威步而言是一个重要的里程碑——公司成立35年以来,一直专注于软件安全及软件授权管理,以保护企业的数字资产与知识产权。展望2025年,数字资产盗窃、数据泄露与网络犯罪等威胁仍在持续增长,威步将在新的形势下继续推动技术…...
线段树(点修,区查,区修)
文章目录 什么是线段树?线段树能够解决什么样的问题?模板 什么是线段树? 线段树是一种二叉搜索树,而二叉搜索树,首先满足二叉树,即每个结点最多有两颗子树,并且是一颗搜索树,我们要知…...
深度学习 - 神经网络的原理
## 深度学习 - 神经网络的原理 深度学习是机器学习的一个分支,其核心是模拟人脑神经网络的结构和功能,构建多层的神经网络模型,从数据中学习特征并进行预测或分类。 **神经网络的基本原理:** 1. **神经元模型:** * 神经网…...
DeepSeek辅助段落扩写的能力怎么样?
DeepSeek-R1在学术写作的诸多细节层面展现出了显著的应用价值。接下来我们将通过一系列具体案例,深入探讨该工具如何在扩写、翻译、发表以及内容改进等关键环节为学术写作提供有力支持。在提问环节,DeepSeek-R1能够高效地简化提示词,并精准地…...
深入Linux系列之进程地址空间
深入Linux系列之进程地址空间 1.引入 那么在之前的学习中,我们知道我们创建一个子进程的话,我们可以在代码层面调用fork函数来创建我们的子进程,那么fork函数的返回值根据我们当前所处进程的上下文是返回不同的值,它在父进程中返…...
虚拟DOM与Diff算法:Vue如何高效更新UI?
虚拟DOM与Diff算法:Vue如何高效更新UI? 虚拟DOM与Diff算法:Vue如何高效更新UI?什么是虚拟DOM?定义虚拟DOM的优势 Diff算法:如何高效计算UI差异定义核心思想Diff算法的步骤示例代码 Vue中的虚拟DOM与Diff算法…...
Golang 并发机制-6:掌握优雅的错误处理艺术
并发编程可能是提高软件系统效率和响应能力的一种强有力的技术。它允许多个工作负载同时运行,充分利用现代多核cpu。然而,巨大的能力带来巨大的责任,良好的错误管理是并发编程的主要任务之一。 并发代码的复杂性 并发编程增加了顺序程序所不…...
【MySQL】第二弹---数据库基础全解析:从概念到实践的深度探索
✨个人主页: 熬夜学编程的小林 💗系列专栏: 【C语言详解】 【数据结构详解】【C详解】【Linux系统编程】【MySQL】 目录 1. 数据库基础 1.1 什么是数据库 1.2 主流数据库 1.3 基本使用 1.3.1 MySQL安装 1.3.2 连接服务器 1.3.3 服务器…...
c++计算机教程
目的 做出-*/%计算机 要求 做出可以计算-*/%的计算机 实现 完整代码 #include<bits/stdc.h> int main() {std::cout<<"加 减- 乘* 除/ 取余% \没有了|(因为可以算三位)"<<"\n"<<"提示:每打完一个符号或打完一个数,\…...
win32汇编环境,对话框程序中自定义工具栏的使用示例三
;运行效果 ;win32汇编环境,对话框程序中自定义工具栏的使用示例三 ;这次是竖着的,以下为生成48*48大小的自定义工具栏图标,自已设计图标样式,显得更专业点。 ;原理是,先生成工具栏控件,再生成图像列表,然后弄几个图标加入图像列表,再把图像列表与工具栏控件关联。需留意…...
集合类不安全问题
ArrayList不是线程安全类,在多线程同时写的情况下,会抛出java.util.ConcurrentModificationException异常 解决办法: 1.使用Vector(ArrayList所有方法加synchronized,太重) 2.使用Collections.synchronized…...
怎么使用Cursor以及升级Cursor pro会员
什么是cursor Cursor:结合AI技术的代码编辑器,助力开发者提升编码效率与质量。作为Visual Studio Code的一个衍生版本,Cursor继承了其用户熟知的界面和插件兼容性,并加入了革命性的AI特性。这款编辑器自2023年1月推出以来&#x…...
启用gui,启动图形化界面
1、停止服务 2、开启maxscale GUI ,修改主配置文件(增加框框内两行) 3、启动服务 注:如果出现以下启动不成功 考虑权限问题 4、访问http://ip:8989 用户名/密码:admin/mariadb...
03-移除元素
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。 假设 nums 中不等于 val 的元素数量为 k,要通过此题,您需要执行以下操作: 更改…...
LSSVM最小二乘支持向量机多变量多步光伏功率预测(Matlab)
代码下载:LSSVM最小二乘支持向量机多变量多步光伏功率预测(Matlab) LSSVM最小二乘支持向量机多变量多步光伏功率预测 一、引言 1.1、研究背景与意义 随着全球能源危机和环境问题的日益严重,可再生能源的开发利用成为了世界各国…...
使用Vue开发可复用的Web Components:跨框架组件封装指南
使用Vue开发可复用的Web Components:跨框架组件封装指南 使用Vue开发可复用的Web Components:跨框架组件封装指南引言什么是Web Components?为什么选择Vue开发Web Components? 封装跨框架组件的步骤1. 创建基本的Vue组件2. 将Vue组…...
用AI写游戏1——js实现贪吃蛇
使用模型通义千问 提示词: 用js html css 做一个贪吃蛇的动画 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Snake Game</title><link rel"stylesheet" href"c…...
星闪开发入门级教程之安装编译器与小项目烧录
系列文章目录 星闪开发入门级教程 好久不见,已经好几年没有发文章了,星闪-作为中国原生的新一代近距离无线联接技术品牌。我想着写点东西。为了适合新手,绝对小白文。 文章目录 系列文章目录前言一、Hispark Studio1.安装Hispark Studio2.安…...
java求职学习day32
JavaScript 详解 课程目标: 1 、 JavaScript 介绍 2 、 HTML 和 JavaScript 结合方式 3 、 JavaScript 的使用 4 、 DOM 操作 5 、 BOM 操作 1. JavaScript介绍 (1)虽然是 java 作为前缀,但 java 和 javascript 的关系,就像老婆和老婆…...
【Markdown语法】锚点机制:跳转任意位置
最近写文章时,发现有一个需求:想要实现一种点击跳转到文档中任意位置的功能,这就是锚点机制,就像游戏中的传送锚点,于是写成文章记录一下使用方式。 本文将详细介绍如何使用Markdown创建文档内部跳转(即锚…...
Docker安装pypiserver私服
Docker安装pypiserver私服 1 简介 Python开源包管理工具有pypiserver、devpi和Nexus等,pypiserver安装部署比较简单,性能也不错。 搭建pypiserver私服,可以自己构建镜像,也可以使用官网的docker镜像。 # Github地址 https://g…...
基于微信小程序的居住证申报系统设计与实现(LW+源码+讲解)
专注于大学生项目实战开发,讲解,毕业答疑辅导,欢迎高校老师/同行前辈交流合作✌。 技术范围:SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容:…...
网站改HTTPS方法
默认的网站建设好后打开的样子那看起来像是钓鱼网站,现在的浏览器特别只能,就是你新买来的电脑默认的浏览器同样也会出现这样“不安全”提示。 传输协议启动了向全球用户安全传输网页内容的流程。然而,随着HTTPS的推出,传输协议通…...