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

/** 查询元素下标* 参数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盘。修改文件路径的时候,共享组件、…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...
