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

数据结构:复杂度的练习(笔记)

数据结构:复杂度的练习(笔记)

例题一:

 

        可以先给数组排序,然后再创建一个i值,让他循环一次++一次,遍历这个排序后的数组,但如果用qsort函数进行排序,时间复杂度就和题目要求的不一致了。所以这个方法行不通

 

        可以将0-n的整数全部相加,然后减去数组中的每个元素,那么就会得到缺失的那个数,此时也会发现时间复杂度是O(N),符合题目的要求。所以这个方法可以

        可以创建一个数组arr2,将题目给的数组arr1内的数字 作为arr2的下标,并且将值放进去。最后如果发现arr2数组内那个坐标没有值,那么就是哪个数。发现时间复杂度也是O(N)。所以这个方法也可以。

        这里将arr1放入arr2,需要循环N次,在这个循环外,需要遍历arr2中缺失的那个数,又需要N次,因此F(N) = 2N  那么时间复杂度就是:O(N)

        相比与思路2,思路3略比逊色。

        异或:相同位0.不同为1 

        两个相同的数字异或是0:x^x=0

        因此,x先和[0,n]异或,就会拿到[0,n]这些数字,也就是x就会被赋予这些数字。当这些数字,再在有缺失的数组中异或,得到的就会是哪个缺失的数字。

        无论数组中的数字是不是[0.n]的顺序,只要期间内和相同的数字异或,那么就会是0。

        如:x^y^b^a^y^a^b==x^y^y^a^a^b^b==x^0^0^0==x(缺失的那个数)

        因此,无论x先和谁异或,只要相同的两个数异或过,那么就相当于异或上0,也就是会被消掉。

        最后时间复杂度:O(N)

就用思路4来写一段代码:

#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>
#include <stdlib.h>
int main()
{int arr1[] = { 9,0,1,8,4,6,5,3,7};//缺失2int x = 0;int n = sizeof(arr1) / sizeof(arr1[0]);//题目中的n是给定的,不算入时间复杂度。for (int i = 0; i <= n; i++){x ^= i;i != n ? x ^= arr1[i] : NULL ;//防止越界访问}printf("%d\n", x);//结果:2return 0;
}

        i != n ? x ^= arr1[i] : NULL ;使用的是三目运算符(条件运算符),当i==n时,arr1并没有arr1[n]元素,如果访问了,就是越界访问,会出现问题。因此当i==时,执行NULL,也就是不执行。

例题二:

对于这道题,有单独的文章:

         C语言题目:左旋字符串._srhqwe的博客-CSDN博客

方法一(对应C语言题目:左旋字符串._srhqwe的博客-CSDN博客的方法一):

        空间复杂度是O(1) :因为空间是可以重复利用的,tmp被释放掉,然后又用tmp。

       时间复杂度是O(N*K):保存变量,然后旋转n-1次,就是N,其中要执行K次,所以是K*N。

方法二:

         开辟一块空间(数组)tmp,将要旋转的个数,对应nums元素的位置,然后直接放到tmp数组,在把nums剩下的元素,再放到tmp数组。

        如此,时间复杂度是O(N)  空间复杂度是O(N),但题目要求空间复杂度是O(1),因此这里并不符合题目的要求。

方法三(三步反转法:对应C语言题目:左旋字符串._srhqwe的博客-CSDN博客的方法二):

        

时间复杂度是:O(N)

空间复杂度是:O(1) 

因为方法1和3在另一篇文章都有,就写一遍方法2,但是!方法2并不符合题目要求。        

#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>
#include <stdlib.h>int main()
{int arr[] = { 1,2,3,4,5,6,7,8,9 };int tmp[20] = { 0 };int sz = sizeof(arr) / sizeof(arr[0]);//元素个数int k = 3;//假如要向左旋转的字符个数为3for(int i = 0;i<sz-k;i++)//将arr后6个,放到tmp的前6个当中{tmp[i] = arr[k + i];}for (int i = 0; i <k ; i++)//将arr前3个,放到tmp后3个中{tmp[sz - k + i] = arr[i];}for (int i = 0; i < sz; i++)//打印tmp的每个元素{printf("%d ", tmp[i]);//结果:4 5 6 7 8 9 1 2 3}//实现反转return 0;
}

相关文章:

数据结构:复杂度的练习(笔记)

数据结构&#xff1a;复杂度的练习&#xff08;笔记&#xff09; 例题一&#xff1a; 可以先给数组排序&#xff0c;然后再创建一个i值&#xff0c;让他循环一次一次&#xff0c;遍历这个排序后的数组&#xff0c;但如果用qsort函数进行排序&#xff0c;时间复杂度就和题目要求…...

JAVA练习69- 从前序与中序遍历序列构造二叉树

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 3月5日练习内容 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、题目-从…...

brew安装问题

最近使用mac安装了Python和PyCharm&#xff0c;使用python中的绘制图像的turtle库后&#xff0c;执行报错&#xff1a; import _tkinter # If this fails your Python may not be configured for Tk ModuleNotFoundError: No module named _tkinter 查询后需在mac 命令行执行&…...

【数据挖掘与商务智能决策】第一章 数据分析与三重工具

numpy基础 numpy与数组 import numpy as np # 用np代替numpy,让代码更简洁 a [1, 2, 3, 4] # 创建列表a b np.array([1, 2, 3, 4]) #从列表ach print(a) print(b) print(type(a)) #打印a类型 print(type(b)) #打印b类型[1, 2, 3, 4] [1 2 3 4] <class ‘list’>…...

计算机底层:BDC码

计算机底层&#xff1a;BDC码 BDC码的作用&#xff1a; 人类喜欢十进制&#xff0c;而机器适合二进制&#xff0c;因此当机器要翻译二进制给人看时&#xff0c;就会进行二进制和十进制的转换&#xff0c;而常规的转换法&#xff08;k*位权&#xff09;太麻烦。因此就出现了不同…...

【C++】平衡二叉搜索(AVL)树的模拟实现

一、 AVL树的概念 map、multimap、set、multiset 在其文档介绍中可以发现&#xff0c;这几个容器有个共同点是&#xff1a;其底层都是按照二叉搜索树来实现的&#xff0c;但是二叉搜索树有其自身的缺陷&#xff0c;假如往树中插入的元素有序或者接近有序&#xff0c;二叉搜索树…...

[2019红帽杯]childRE

题目下载&#xff1a;下载 参考&#xff1a;re学习笔记&#xff08;24&#xff09;BUUCTF-re-[2019红帽杯]childRE_Forgo7ten的博客-CSDN博客 这道题涉及到c函数的修饰规则&#xff0c;按照规则来看应该是比较容易理解的。上面博客中有总结规则&#xff0c;可以学习一下。 载…...

2D图像处理:九点标定_下(机械手轴线与法兰轴线不重合)(附源码)

文章目录 2. 机械手轴线与法兰轴线不重合2.1 两次拍照避免标定旋转中心2.2 旋转中心标定2.3 非标定中心的方法2.3.1 预备内容-点坐标旋转计算2.3.2 工件存在平移和旋转3. 代码(待更新)上一篇:2D图像处理:九点标定_上(机械手轴线与法兰轴线重合)(附源码) 2. 机械手轴线…...

【二分查找】分巧克力、机器人跳跃、数的范围

Halo&#xff0c;这里是Ppeua。平时主要更新C语言&#xff0c;C&#xff0c;数据结构算法......感兴趣就关注我吧&#xff01;你定不会失望。 &#x1f308;个人主页&#xff1a;主页链接 &#x1f308;算法专栏&#xff1a;专栏链接 我会一直往里填充内容哒&#xff01; &…...

Hyperf使用RabbitMQ消息队列

Hyperf连接使用RabbitMQ消息中间件 传送门 使用Docker部署RabbitMQ&#xff0c;->传送门<使用Docker部署Hyperf&#xff0c;->传送门-< 部署环境 安装amqp扩展 composer require hyperf/amqp安装command命令行扩展 composer require hyperf/command配置参数 假…...

【Linux】P3 用户与用户组

用户与用户组root 超级管理员设置超级管理员密码切换到超级管理员sudo 临时使用超级权限用户与用户组用户组管理用户管理getentroot 超级管理员 设置超级管理员密码 登陆后不会自动开启 root 访问权限&#xff0c;需要首先执行如下步骤设定 root 超级管理员密码 1、解除 roo…...

Spring核心模块——Aware接口

Aware接口前言基本内容例子结尾前言 Spring的依赖注入最大亮点是所有的Bean对Spring容器对存在都是没有意识到&#xff0c;Spring容器中的Bean的耦合度是很低的&#xff0c;我们可以将Spring容器很容易换成其他的容器。 但是实际开发的时候&#xff0c;我们经常要用到Spring容…...

Linux网络编程 第六天

目录 学习目标 libevent介绍 libevent的安装 libevent库的使用 libevent的使用 libevent的地基-event_base 等待事件产生-循环等待event_loop 使用libevent库的步骤&#xff1a; 事件驱动-event 编写一个基于event实现的tcp服务器&#xff1a; 自带buffer的事件-buff…...

STM32开发(六)STM32F103 通信 —— RS485 Modbus通信编程详解

文章目录一、基础知识点二、开发环境三、STM32CubeMX相关配置1、STM32CubeMX基本配置2、STM32CubeMX RS485 相关配置四、Vscode代码讲解五、结果演示以及报文解析一、基础知识点 了解 RS485 Modbus协议技术 。本实验是基于STM32F103开发 实现 通过RS-485实现modbus协议。 准备…...

AcWing1049.大盗阿福题解

前言如果想看状态机的详解&#xff0c;点机这里:dp模型——状态机模型C详解1049. 大盗阿福阿福是一名经验丰富的大盗。趁着月黑风高&#xff0c;阿福打算今晚洗劫一条街上的店铺。这条街上一共有 N家店铺&#xff0c;每家店中都有一些现金。阿福事先调查得知&#xff0c;只有当…...

python日志模块,loggin模块

python日志模块&#xff0c;loggin模块loggin模块日志的格式处理器种类日志格式的参数使用loggin模块 logging库采用模块化方法&#xff0c;并提供了几类组件&#xff1a;记录器&#xff0c;处理程序&#xff0c;过滤器和格式化程序。 记录器&#xff08;Logger&#xff09;&a…...

接口自动化入门-TestNg

目录1.TestNg介绍2、TestNG安装3、TestNG使用3.1 编写测试用例脚本3.2 创建TestNG.xml文件&#xff08;1&#xff09;创建testng.xml文件&#xff08;2&#xff09;修改testng.xml4、测试报告生成1.TestNg介绍 TestNg是Java中开源的自动化测试框架&#xff0c;灵感来源于Junit…...

Spring AOP —— 详解、实现原理、简单demo

目录 一、Spring AOP 是什么&#xff1f; 二、学习AOP 有什么作用&#xff1f; 三、AOP 的组成 3.1、切面&#xff08;Aspect&#xff09; 3.2、切点&#xff08;Pointcut&#xff09; 3.3、通知&#xff08;Advice&#xff09; 3.4、连接点 四、实现 Spring AOP 一个简…...

(蓝桥真题)异或数列(博弈)

题目链接&#xff1a;P8743 [蓝桥杯 2021 省 A] 异或数列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 样例输入&#xff1a; 4 1 1 1 0 2 2 1 7 992438 1006399 781139 985280 4729 872779 563580 样例输出&#xff1a; 1 0 1 1 分析&#xff1a;容易想到对于异或最大值…...

4万字数字政府建设总体规划方案WORD

本资料来源公开网络&#xff0c;仅供个人学习&#xff0c;请勿商用。部分资料内容&#xff1a; 我省“数字政府”架构 &#xff08;一&#xff09; 总体架构。 “数字政府”总体架构包括管理架构、业务架构、技术架构。其中&#xff0c;管理架构体现“管运分离”的建设运营模式…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

【Linux】自动化构建-Make/Makefile

前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具&#xff1a;make/makfile 1.背景 在一个工程中源文件不计其数&#xff0c;其按类型、功能、模块分别放在若干个目录中&#xff0c;mak…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...

AxureRP-Pro-Beta-Setup_114413.exe (6.0.0.2887)

Name&#xff1a;3ddown Serial&#xff1a;FiCGEezgdGoYILo8U/2MFyCWj0jZoJc/sziRRj2/ENvtEq7w1RH97k5MWctqVHA 注册用户名&#xff1a;Axure 序列号&#xff1a;8t3Yk/zu4cX601/seX6wBZgYRVj/lkC2PICCdO4sFKCCLx8mcCnccoylVb40lP...

OCR MLLM Evaluation

为什么需要评测体系&#xff1f;——背景与矛盾 ​​ 能干的事&#xff1a;​​ 看清楚发票、身份证上的字&#xff08;准确率>90%&#xff09;&#xff0c;速度飞快&#xff08;眨眼间完成&#xff09;。​​干不了的事&#xff1a;​​ 碰到复杂表格&#xff08;合并单元…...