算法||实现典型数据结构的查找、添加和删除数据 并分析其时间和空间复杂度
实现典型数据结构的查找、添加和删除数据 并分析其时间和空间复杂度
- 线性结构:
数组:是一种线性表数据结构,它用一组连续的内存空间,来存储一组具有相同类型的数据。
- 查找数据 :随机访问
- 流程图

/** 查询元素下标* 参数1:Array_t数组结构体指针* 参数2:元素值* 返回:成功返回元素下标,失败返回-1*/
int search(struct Array_t *array, int elem){int idx = 0;// 遍历数组for (idx = 0; idx < array->used; idx++){// 找到与查询的元素值相同的数组元素,则返回元素下标if (array->arr[idx] == elem){return idx;}// 如果数组元素大于新元素,说明未找到此数组下标, 则提前报错退出// 因为本例子的数组是有序从小到大的if (array->arr[idx] > elem){break;}}// 遍历完,说明未找到此数组下标,则报错退出std::cout << "ERROR: No search to this" << elem << " elem." << std::endl;return -1;
}
- 复杂度分析(时间和空间)
时间复杂度:已知索引 O(1);未知索引 O(n);
空间复杂度:O(n)。
2.添加数据
- 流程图

/** 插入新元素* 参数1:Array_t数组结构体指针* 参数2:新元素的值* 返回:成功返回插入的数组下标,失败返回-1*/
int insertElem(struct Array_t *array, int elem){// 当数组被占用数大于等于数组长度时,说明数组所有下标都已存放数据了,无法在进行插入if (array->used >= array->length){std::cout << "ERROR: array size is full, can't insert " << elem << " elem." << std::endl;return -1;}int idx = 0;// 遍历数组,找到大于新元素elem的下标idxfor (idx = 0; idx < array->used; idx++){// 如果找到数组元素的值大于新元素elem的值,则退出if (array->arr[idx] > elem){break;}}// 如果插入的下标的位置不是在末尾,则需要把idx之后的// 数据依次往后搬移一位,空出下标为idx的元素待后续插入if (idx < array->used){// 将idx之后的数据依次往后搬移一位memmove(&array->arr[idx + 1], &array->arr[idx], (array->used - idx) * sizeof(int));}// 插入元素array->arr[idx] = elem;// 被占用数自增array->used++;// 成功返回插入的数组下标return idx;
}
- 复杂度分析)
时间复杂度:未知索引 O(n);
空间复杂度:O(n)。
- 可以改进
我们的数组是无序的,插入一个元素也不在乎顺序,也没有指定插入元素的位置,那么这时候就可以选择直接插入尾部;如果插入元素时指定了一个插入位置,如果不关心顺序的话也可以采用一种巧妙的办法来实现:
public static void addByElement(int[] arr, int size, int index,int element) {if (null == arr || arr.length == 0){//数组是否为空return;}if (size >= arr.length){//确认数组至少有一个空位return;}arr[size] = arr[index];//将 index 和有效数组位数的最后一位交换arr[index] = element;
这里其实就是直接将需要插入元素的位置上的原有元素放到最后,然后再直接插入,避免了数组的移动,实现了 O(1) 时间复杂度的插入。
3.删除数据
- 流程图

/** 删除新元素* 参数1:Array_t数组结构体指针* 参数2:删除元素的数组下标位置* 返回:成功返回0,失败返回-1*/
int deleteElem(struct Array_t *array, int idx){// 判断下标位置是否合法if (idx < 0 || idx >= array->used){std::cout << "ERROR:idx[" << idx << "] not in the range of arrays." << std::endl;return -1;}// 将idx下标之后的数据往前搬移一位memmove(&array->arr[idx], &array->arr[idx + 1], (array->used - idx - 1) * sizeof(int));// 数组占用个数减1array->used--;return 0;
}
- 复杂度分析
时间复杂度:O(n);
空间复杂度:O(n)。
相关文章:
算法||实现典型数据结构的查找、添加和删除数据 并分析其时间和空间复杂度
实现典型数据结构的查找、添加和删除数据 并分析其时间和空间复杂度 线性结构: 数组:是一种线性表数据结构,它用一组连续的内存空间,来存储一组具有相同类型的数据。 查找数据 :随机访问 流程图 /** 查询元素下标…...
【蓝桥杯冲冲冲】Invasion of the Milkweed G
【蓝桥杯冲冲冲】Invasion of the Milkweed G 蓝桥杯备赛 | 洛谷做题打卡day30 文章目录 蓝桥杯备赛 | 洛谷做题打卡day30[USACO09OCT] Invasion of the Milkweed G题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 题解代码我的一些话 [USACO09OCT] Invasion of the Mi…...
【JAVA WEB】 百度热榜实现 新闻页面 Chrome 调试工具
目录 百度热榜 新闻页面 Chrome 调试工具 --查看css属性 打开调试工具的方式 标签页含义 百度热榜 实现效果: 实现代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"vi…...
Linux——动静态库
基础知识:动vs静 类型动静加载时机运行时编译时可复用性多个文件只需要加载一份库文件每个文件都需要加载一份文件性能链接次数越多越有优势链接次数越少越有优势 代码编写 静态库 生成静态库 libmath.a:add.o sub.oar -rc $ $^%.o:%.cgcc -c $<使用静态库 头文件和工…...
Vulnhub靶机:hacksudo-search
一、介绍 运行环境:Virtualbox 攻击机:kali(10.0.2.15) 靶机:hacksudo-search(10.0.2.50) 目标:获取靶机root权限和flag 靶机下载地址:https://download.vulnhub.co…...
Leetcode 188 买卖股票的最佳时机 IV
题意理解: 给你一个整数数组 prices 和一个整数 k ,其中 prices[i] 是某支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说,你最多可以买 k 次,卖 k 次。 注意…...
win32编程系统BUG(Win32 API中的WM_SETTEXT消息)
由于频繁使用Win32 API中的WM_SETTEXT消息,导致内存占用直线上升。 暂未找到有效解决方案。...
Linux防火墙开放
记录一次问题 写的网络服务无法通信 代码没问题,IP绑定、端口绑定没问题,就是无法进行通信,这里要分2步走。 服务器控制台开放 进入防火墙 添加规则,这里以开放udp的8899端口为例 这里在服务器后台就已经开放了,但此时…...
通过 docker-compose 部署 Flink
概要 通过 docker-compose 以 Session Mode 部署 flink 前置依赖 Docker、docker-composeflink 客户端docker-compose.yml version: "2.2" services:jobmanager:image: flink:1.17.2ports:- "8081:8081"command: jobmanagervolumes:- ${PWD}/checkpoin…...
HarmonyOS ArkTS修改App的默认加载的界面(二十)
前言:在Android开发中想要修改默认启动页,只需要在AndroidManifest.xml中设置即可 只需要在启动的activity种添加如下属性即可 <intent-filter><action android:name"android.intent.action.MAIN" /><category android:name&qu…...
【前端高频面试题--Vue基础篇】
🚀 作者 :“码上有前” 🚀 文章简介 :前端高频面试题 🚀 欢迎小伙伴们 点赞👍、收藏⭐、留言💬前端高频面试题--Vue基础篇 Vue基本原理双向绑定与MVVM模型Vue的优点计算属性与监听属性计算属性监…...
Spring Boot 实现热插拔 AOP
现在有这么一个需求:就是我们日志的开与关是交给使用人员来控制的,而不是由我们开发人员固定写死的。大家都知道可以用aop来实现日志管理,但是如何动态的来实现日志管理呢?aop源码中的实现逻辑中有这么一个步骤,就是会依次扫描Advice的实现类,然后执行。我们要做的就是自…...
2月05日,每日信息差
第一、全球首套5G及6G天地一体网络低轨试验卫星发射入轨、。据了解,“中国移动01星”是全球首颗可验证5G天地一体演进技术的试验卫星,它搭载的基站可以利用卫星的广覆盖优势把5G信号传送到地面网络无法覆盖到的地方;另外一颗“‘星核’验证星…...
使用Python进行数据的描述性分析,用少量的描述性指标来概括大量的原始数据
在进行数据分析时,当研究者得到的数据量很小时,可以通过直接观察原始数据来获得所有的信息。但是,当得到的数据量很大时,就必须借助各种描述性指标来完成对数据的描述工作。用少量的描述性指标来概括大量的原始数据,对…...
【JS逆向三】逆向某某网站的sign参数,并模拟生成仅供学习
逆向日期:2024.02.06 使用工具:Node.js 类型:webpack 文章全程已做去敏处理!!! 【需要做的可联系我】 可使用AES进行解密处理(直接解密即可):AES加解密工具 1、打开某某…...
移动光猫gs3101超级密码及改桥接模式教程
文章目录 超级管理员账号改桥接模式路由器连接光猫,PPPOE拨号即可!附录:如果需要改桥接的话不知道拨号密码咋办打开光猫Telnet功能Telnet 登录 参考文章 移动光猫吉比特GS3101超级账号获取更改桥接 移动光猫gs3101超级密码及改桥接模式教程 …...
leetcode 153
153 寻找旋转排序数组中的最小值 这道题,如果我们熟悉数组 api,可以直接用 Arrays.sort()秒杀,这个方法使用了双轴快速排序算法。 解法1如下: class Solution {public int findMin(int[] nums) {Arrays.sort(nums);return nums…...
【MySQL】数据库的基础——数据库的介绍、MySQL的介绍和架构、SQL分类、MySQL的基本使用、MySQL的存储引擎
文章目录 MySQL1. 数据库的介绍1.2 主流数据库 2. MySQL的介绍2.1 MySQL架构2.2 SQL分类2.3 MySQL的基本使用2.4 MySQL存储引擎 MySQL 1. 数据库的介绍 数据库(Database,简称DB)是按照数据结构来组织、存储和管理数据的仓库。它是长期存储在计…...
后端的技术设计文档
一、 背景 1.简介 2.业务规划(非必需) 3.工作项拆解 拆解成多个工作项,每个工作项,需要多少人力。 4.资源评估(非必需) 有没有新的服务 二、架构设计 1.架构图(非必需,新服务比较需要) 2.技术选型 SpringCloud、Redis、Mysql、Myba…...
Windows10安装PCL1.14.0及点云配准
一、下载visual studio2022 下载网址:Visual Studio: 面向软件开发人员和 Teams 的 IDE 和代码编辑器 (microsoft.com) 安装的时候选择"使用C的桌面开发“,同时可以修改文件路径,可以放在D盘。修改文件路径的时候,共享组件、…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
