当前位置: 首页 > news >正文

算法||实现典型数据结构的查找、添加和删除数据 并分析其时间和空间复杂度

实现典型数据结构的查找、添加和删除数据 并分析其时间和空间复杂度

  • 线性结构:

数组:是一种线性表数据结构,它用一组连续的内存空间,来存储一组具有相同类型的数据。

  1. 查找数据 :随机访问
  • 流程图

/**  查询元素下标*  参数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)

相关文章:

算法||实现典型数据结构的查找、添加和删除数据 并分析其时间和空间复杂度

实现典型数据结构的查找、添加和删除数据 并分析其时间和空间复杂度 线性结构&#xff1a; 数组&#xff1a;是一种线性表数据结构&#xff0c;它用一组连续的内存空间&#xff0c;来存储一组具有相同类型的数据。 查找数据 &#xff1a;随机访问 流程图 /** 查询元素下标…...

【蓝桥杯冲冲冲】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属性 打开调试工具的方式 标签页含义 百度热榜 实现效果&#xff1a; 实现代码 <!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

一、介绍 运行环境&#xff1a;Virtualbox 攻击机&#xff1a;kali&#xff08;10.0.2.15&#xff09; 靶机&#xff1a;hacksudo-search&#xff08;10.0.2.50&#xff09; 目标&#xff1a;获取靶机root权限和flag 靶机下载地址&#xff1a;https://download.vulnhub.co…...

Leetcode 188 买卖股票的最佳时机 IV

题意理解&#xff1a; 给你一个整数数组 prices 和一个整数 k &#xff0c;其中 prices[i] 是某支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说&#xff0c;你最多可以买 k 次&#xff0c;卖 k 次。 注意&#xf…...

win32编程系统BUG(Win32 API中的WM_SETTEXT消息)

由于频繁使用Win32 API中的WM_SETTEXT消息&#xff0c;导致内存占用直线上升。 暂未找到有效解决方案。...

Linux防火墙开放

记录一次问题 写的网络服务无法通信 代码没问题&#xff0c;IP绑定、端口绑定没问题&#xff0c;就是无法进行通信&#xff0c;这里要分2步走。 服务器控制台开放 进入防火墙 添加规则&#xff0c;这里以开放udp的8899端口为例 这里在服务器后台就已经开放了&#xff0c;但此时…...

通过 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的默认加载的界面(二十)

前言&#xff1a;在Android开发中想要修改默认启动页&#xff0c;只需要在AndroidManifest.xml中设置即可 只需要在启动的activity种添加如下属性即可 <intent-filter><action android:name"android.intent.action.MAIN" /><category android:name&qu…...

【前端高频面试题--Vue基础篇】

&#x1f680; 作者 &#xff1a;“码上有前” &#x1f680; 文章简介 &#xff1a;前端高频面试题 &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac;前端高频面试题--Vue基础篇 Vue基本原理双向绑定与MVVM模型Vue的优点计算属性与监听属性计算属性监…...

Spring Boot 实现热插拔 AOP

现在有这么一个需求:就是我们日志的开与关是交给使用人员来控制的,而不是由我们开发人员固定写死的。大家都知道可以用aop来实现日志管理,但是如何动态的来实现日志管理呢?aop源码中的实现逻辑中有这么一个步骤,就是会依次扫描Advice的实现类,然后执行。我们要做的就是自…...

2月05日,每日信息差

第一、全球首套5G及6G天地一体网络低轨试验卫星发射入轨、。据了解&#xff0c;“中国移动01星”是全球首颗可验证5G天地一体演进技术的试验卫星&#xff0c;它搭载的基站可以利用卫星的广覆盖优势把5G信号传送到地面网络无法覆盖到的地方&#xff1b;另外一颗“‘星核’验证星…...

使用Python进行数据的描述性分析,用少量的描述性指标来概括大量的原始数据

在进行数据分析时&#xff0c;当研究者得到的数据量很小时&#xff0c;可以通过直接观察原始数据来获得所有的信息。但是&#xff0c;当得到的数据量很大时&#xff0c;就必须借助各种描述性指标来完成对数据的描述工作。用少量的描述性指标来概括大量的原始数据&#xff0c;对…...

【JS逆向三】逆向某某网站的sign参数,并模拟生成仅供学习

逆向日期&#xff1a;2024.02.06 使用工具&#xff1a;Node.js 类型&#xff1a;webpack 文章全程已做去敏处理&#xff01;&#xff01;&#xff01; 【需要做的可联系我】 可使用AES进行解密处理&#xff08;直接解密即可&#xff09;&#xff1a;AES加解密工具 1、打开某某…...

移动光猫gs3101超级密码及改桥接模式教程

文章目录 超级管理员账号改桥接模式路由器连接光猫&#xff0c;PPPOE拨号即可&#xff01;附录&#xff1a;如果需要改桥接的话不知道拨号密码咋办打开光猫Telnet功能Telnet 登录 参考文章 移动光猫吉比特GS3101超级账号获取更改桥接 移动光猫gs3101超级密码及改桥接模式教程 …...

leetcode 153

153 寻找旋转排序数组中的最小值 这道题&#xff0c;如果我们熟悉数组 api&#xff0c;可以直接用 Arrays.sort()秒杀&#xff0c;这个方法使用了双轴快速排序算法。 解法1如下&#xff1a; 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. 数据库的介绍 数据库&#xff08;Database&#xff0c;简称DB&#xff09;是按照数据结构来组织、存储和管理数据的仓库。它是长期存储在计…...

后端的技术设计文档

一、 背景 1.简介 2.业务规划(非必需) 3.工作项拆解 拆解成多个工作项&#xff0c;每个工作项&#xff0c;需要多少人力。 4.资源评估(非必需) 有没有新的服务 二、架构设计 1.架构图(非必需&#xff0c;新服务比较需要) 2.技术选型 SpringCloud、Redis、Mysql、Myba…...

Windows10安装PCL1.14.0及点云配准

一、下载visual studio2022 下载网址&#xff1a;Visual Studio: 面向软件开发人员和 Teams 的 IDE 和代码编辑器 (microsoft.com) 安装的时候选择"使用C的桌面开发“&#xff0c;同时可以修改文件路径&#xff0c;可以放在D盘。修改文件路径的时候&#xff0c;共享组件、…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

__VUE_PROD_HYDRATION_MISMATCH_DETAILS__ is not explicitly defined.

这个警告表明您在使用Vue的esm-bundler构建版本时&#xff0c;未明确定义编译时特性标志。以下是详细解释和解决方案&#xff1a; ‌问题原因‌&#xff1a; 该标志是Vue 3.4引入的编译时特性标志&#xff0c;用于控制生产环境下SSR水合不匹配错误的详细报告1使用esm-bundler…...

LeetCode 0386.字典序排数:细心总结条件

【LetMeFly】386.字典序排数&#xff1a;细心总结条件 力扣题目链接&#xff1a;https://leetcode.cn/problems/lexicographical-numbers/ 给你一个整数 n &#xff0c;按字典序返回范围 [1, n] 内所有整数。 你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。…...

基于django+vue的健身房管理系统-vue

开发语言&#xff1a;Python框架&#xff1a;djangoPython版本&#xff1a;python3.8数据库&#xff1a;mysql 5.7数据库工具&#xff1a;Navicat12开发软件&#xff1a;PyCharm 系统展示 会员信息管理 员工信息管理 会员卡类型管理 健身项目管理 会员卡管理 摘要 健身房管理…...

信息系统分析与设计复习

2024试卷 单选题&#xff08;20&#xff09; 1、在一个聊天系统(类似ChatGPT)中&#xff0c;属于控制类的是&#xff08;&#xff09;。 A. 话语者类 B.聊天文字输入界面类 C. 聊天主题辨别类 D. 聊天历史类 ​解析 B-C-E备选架构中分析类分为边界类、控制类和实体类。 边界…...