【数据结构】时间复杂度---OJ练习题
目录
🌴时间复杂度练习
📌面试题--->消失的数字
题目描述
题目链接:面试题 17.04. 消失的数字
🌴解题思路
📌思路1:
malloc函数用法
📌思路2:
📌思路3:
🌴时间复杂度练习
🙊 如果有不了解时间复杂度的请移步上一篇文章:【数据结构】初识
📌面试题--->消失的数字
题目描述
数组nums包含从0到n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗?
题目链接:面试题 17.04. 消失的数字
示例 1:
输入:
[3,0,1]
输出:
2
示例 2:
输入:
[9,6,4,2,3,5,7,0,1]
输出:
8
🌴解题思路
📌思路1:
1.开辟一个额外的N+1个数的数组(即malloc一个额外N+1个数的数组),建立一个映射关系,,将数组的值全部初始化为-1
2.遍历这些数字,这个数是多少就写到数组的对应位置
3.再遍历一遍数组,哪个位置是-1,哪个位置的下表就是缺失的数字
因为malloc数组基本没有时间消耗,但是初始化时需要循环N+1次,填数字的时候也循环了N+1次,最后遍历时最坏也要循环N+1次,总共3N+3次,根据大O的渐进表示法就知道时间复杂度O(N)。
时间复杂度是:O(N)
代码展示:
int missingNumber(int* nums, int numsSize){int* p = (int*)malloc((numsSize+1) * sizeof(int));for(int i=0;i<=numsSize;i++){p[i]=-1;}for(int i=0;i<numsSize;i++){p[nums[i]]=nums[i];}for(int i=0;i<=numsSize;i++){if(p[i]==-1){free(p);return i;}}free(p);return -1;
}
结果:

malloc函数用法
函数声明:
void *malloc(size_t size)
头文件: <stdlib.h>
参数:
size --- 内存块的大小,以字节为单位。
返回值:
该函数返回一个指针 ,指向已分配大小的内存。为避免内存泄漏,必须用 free() 或 realloc() 解分配返回的指针。如果请求失败,则返回 NULL。
示例:
double * pt;
pt = (double * ) malloc (30 * sizeof(double));
这段代码请求30个double类型值的空间,并且让pt指向该空间所在位置。
在释放空间时只需如下操作:
free(pt);
📌思路2:
异或:------>符号:^
用一个 x = 0,x跟数组中的这些数据都异或一遍,
然后再跟0-N之间的数字异或一遍,最后x才是缺失的数字。
注意:❗️0^x = x ❗️ a^a = 0
❗️异或满足交换律和结合律(即1^2^3^1^2 = 1^1^2^2^3 =3)
因为第一遍异或时需要循环N次,第二遍也需要N次,总共2N次,根据大O的渐进表示法就知道时间复杂度为O(N)。
时间复杂度:O(N)
代码展示:
int missingNumber(int* nums, int numsSize){int x=0;for(int i = 0;i < numsSize; ++i){x ^= nums[i];}for(int j = 0;j < numsSize+1; ++j){x ^= j;}return x;
}
注意: 这里* nums表示存放0-N中缺失了一个数字后的所有数字的数组,一共有numsSize个,而0-N之间一共有numsSize+1个数。
结果:

📌思路3:
公式计算:
1.求0-N这些数的和(利用求和公式)
2.再求数组中存放的这些数的和(用for循环)
3.将第一次求的和减去第二次求的和即为缺失的数字
因为第一次求和使用公式所以基本不消耗时间,第二次求和进行了N次循环,总共N次,根据大O的渐进表示法就知道时间复杂度为O(N)。
时间复杂度:O(N)
代码展示:
int missingNumber(int* nums, int numsSize){
int sum = ((numsSize + 1) * numsSize) / 2;
for (int i = 0;i< numsSize; ++i)
{sum -=*(nums+i);
}
return sum;
}
结果:

🔥今天的分享就到这里,如果觉得博主的文章还不错的话,请👍三连支持一下博主哦🤞

相关文章:
【数据结构】时间复杂度---OJ练习题
目录 🌴时间复杂度练习 📌面试题--->消失的数字 题目描述 题目链接:面试题 17.04. 消失的数字 🌴解题思路 📌思路1: malloc函数用法 📌思路2: 📌思路3&…...
京东自动化功能之商品信息监控是否有库存
这里有两个参数,分别是area和skuids area是地区编码,我这里统计了全国各个区县的area编码,用户可以根据实际地址进行构造skuids是商品的信息ID填写好这两个商品之后,会显示两种状态,判断有货或者无货状态,详情如下图所示 简单编写下python代码,比如我们的地址是北京市…...
【SwitchyOmega】SwitchyOmega 安装及使用
文章目录 安装教程使用教程 安装教程 SwitchyOmega 谷歌商店下载链接:https://chrome.google.com/webstore/detail/proxy-switchyomega/padekgcemlokbadohgkifijomclgjgif?hlen-US 在谷歌商店搜索 SwitchyOmega, 选择 Proxy SwitchyOmega 点击 Add t…...
CentOS5678 repo源 地址 阿里云开源镜像站
CentOS5678 repo 地址 阿里云开源镜像站 https://mirrors.aliyun.com/repo/ CentOS-5.repo https://mirrors.aliyun.com/repo/Centos-5.repo [base] nameCentOS-$releasever - Base - mirrors.aliyun.com failovermethodpriority baseurlhttp://mirrors.aliyun.com/centos/$r…...
【LLM】Langchain使用[二](模型链)
文章目录 1. SimpleSequentialChain2. SequentialChain3. 路由链 Router Chain Reference 1. SimpleSequentialChain 场景:一个输入和一个输出 from langchain.chat_models import ChatOpenAI #导入OpenAI模型 from langchain.prompts import ChatPromptTempla…...
简单机器学习工程化过程
1、确认需求(构建问题) 我们需要做什么? 比如根据一些输入数据,预测某个值? 比如输入一些特征,判断这个是个什么动物? 这里我们要可以尝试分析一下,我们要处理的是个什么问题&…...
【MongoDB】SpringBoot整合MongoDB
【MongoDB】SpringBoot整合MongoDB 文章目录 【MongoDB】SpringBoot整合MongoDB0. 准备工作1. 集合操作1.1 创建集合1.2 删除集合 2. 相关注解3. 文档操作3.1 添加文档3.2 批量添加文档3.3 查询文档3.3.1 查询所有文档3.3.2 根据id查询3.3.3 等值查询3.3.4 范围查询3.3.5 and查…...
关于游戏引擎(godot)对齐音乐bpm的技术
引擎默认底层 1. _process(): 每秒钟调用60次(无限的) 数学 1. bpm1分钟节拍数量60s节拍数量 bpm120 60s120拍 2. 每拍子时间 60/bpm 3. 每个拍子触发周期所需要的帧数 每拍子时间*60(帧率) 这个是从帧数级别上对齐拍子的时间&#x…...
【Go】实现一个代理Kerberos环境部分组件控制台的Web服务
实现一个代理Kerberos环境部分组件控制台的Web服务 背景安全措施引入的问题SSO单点登录 过程整体设计路由反向代理登录会话组件代理YarnHbase 结果 背景 首先要说明下我们目前有部分集群的环境使用的是HDP-3.1.5.0的大数据集群,除了集成了一些自定义的服务以外&…...
Spring Security 6.x 系列【63】扩展篇之匿名认证
有道无术,术尚可求,有术无道,止于术。 本系列Spring Boot 版本 3.1.0 本系列Spring Security 版本 6.1.0 本系列Spring Authorization Server 版本 1.1.0 源码地址:https://gitee.com/pearl-organization/study-spring-security-demo 文章目录 1. 概述2. 配置3. Anonymo…...
供应链管理系统有哪些?
1万字干货分享,国内外 20款 供应链管理软件都给你讲的明明白白。如果你还不知道怎么选择,一定要翻到第三大段,这里我将会通过8年的软件产品选型经验告诉你,怎么样才能快速选到适合自己的软件工具。 (为防后续找不到&a…...
如何在PADS Logic中查找器件
PADS Logic提供类似于Windows的查找功能,可以进行器件的查找。 (1)在Logic设计界面中,将菜单显示中的“选择工具栏”进行打开,如图1所示,会弹出对应的“选择工具栏”的分栏菜单选项,如图2所示。…...
Android 生成pdf文件
Android 生成pdf文件 1.使用官方的方式 使用官方的方式也就是PdfDocument类的使用 1.1 基本使用 /**** 将tv内容写入到pdf文件*/RequiresApi(api Build.VERSION_CODES.KITKAT)private void newPdf() {// 创建一个PDF文本对象PdfDocument document new PdfDocument();//创建…...
Kafka 入门到起飞 - 生产者发送消息流程解析
生产者通过send()方法发送消息消息会经过拦截器->序列化器->分区器 进行加工然后将消息存在缓冲区当缓冲区中消息达到条件会按批次发送到broker对应分区上broker将接收到的消息进行刷盘持久化消息处理broker会返回给producer响应落盘成功返回元数据…...
基于单片机智能台灯坐姿矫正器视力保护器的设计与实现
功能介绍 以51单片机作为主控系统;LCD1602液晶显示当前当前光线强度、台灯灯光强度、当前时间、坐姿距离等;按键设置当前时间,闹钟、提醒时间、坐姿最小距离;通过超声波检测坐姿,当坐姿不正容易对眼睛和身体腰部等造成…...
欧姆龙以太网模块如何设置ip连接 Kepware opc步骤
在数字化和自动化的今天,PLC在工业控制领域的作用日益重要。然而,PLC通讯口的有限资源成为了困扰工程师们的问题。为了解决这一问题,捷米特推出了JM-ETH-CP转以太网模块,让即插即用的以太网通讯成为可能,不仅有效利用了…...
PLEX如何搭建个人局域网的视频网站
Plex是一款功能非常强大的影音媒体管理系统,最大的优势是多平台支持和界面优美,几乎可以在所有的平台上安装plex服务器和客户端,让你可以随时随地享受存储在家中的电影、照片、音乐,并且可以实现观看记录无缝衔接,手机…...
java学习02
一、基本数据类型 Java有两大数据类型,内置数据类型和引用数据类型。 内置数据类型 Java语言提供了八种基本类型。六种数字类型(四个整数型,两个浮点型),一种字符类型,还有一种布尔型。 byte࿱…...
libcurl库使用实例
libcurl libcurl是一个功能强大的跨平台网络传输库,支持多种协议,包括HTTP、FTP、SMTP等,同时提供了易于使用的API。 安装 ubuntu18.04平台安装 sudo apt-get install libcurl4-openssl-dev实例 这个示例使用libcurl库发送一个简单的HTTP …...
大数据存储架构详解:数据仓库、数据集市、数据湖、数据网格、湖仓一体
前言 本文隶属于专栏《大数据理论体系》,该专栏为笔者原创,引用请注明来源,不足和错误之处请在评论区帮忙指出,谢谢! 本专栏目录结构和参考文献请见大数据理论体系 思维导图 数据仓库 数据仓库是一个面向主题的&…...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
