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

数据结构----结构--线性结构--顺序存储--数组

数据结构----结构–线性结构–顺序存储–数组

数组:类型相同,空间连续,长度固定

搜索:

(1)基于索引搜索,时间复杂度O(1)

(2)基于数值搜索:

​ 1.有序的:二分查找

​ 2.无需的:遍历一遍O(n)

增删:

​ 空间不够:扩容 旧数据->新数据 迁移

​ 空间足够:尾增尾删O(1) 其他增删O(n)

关于数组特性的题

第一题

题目:给一个有n个元素的数组,数组内的元素数值范围在0~n-1之间。请检测:数据有无重复出现,如果出现请报错

解决方法:1.暴力 时间复杂度O(n的平方) 空间复杂度 O(1)

​ 2.计数 时间复杂度O(n) 空间复杂度 O(n)

​ 3.排序: 时间复杂度O(看利用哪种排序) 空间复杂度 O(看利用哪种排序)

​ 4.set/map 时间复杂度O(nlog2的n次方) 空间复杂度O(nlog2的n次方)

​ 5.交换 时间复杂度O(n) 空间复杂度 O(1)

这里交换的方法最好 我们用代码实现一下

#include<iostream>
using namespace std;//判断的函数
void PanDuan(int a[],int length) {for (int i = 0; i < length;) {//遍历if (a[i] == i) {//如果下标和数对上了就下一个i++;}else {if (a[i] == a[a[i]]) {//重复cout << "错误" << endl;break;}else {//不重复交换位置int t;t = a[i];a[i] = a[a[i]];a[t] = t;}}
}
int main() {int a[] = { 0,3,2,4,1 };//定义一个数组,进行测试PanDuan(a,(sizeof(a)/sizeof(a[0])));//进入判断的函数return 0;
}

第二题

题目:一组数据,其中有一个元素只出现一次,其他元素均出现两次,请找出只出现一次的元素

解决方法:1.暴力 时间复杂度O(n的平方) 空间复杂度 O(1)

​ 2.计数 (哈希表,map)

​ 哈希表 时间复杂度O(n) 空间复杂度 O(n)

​ map 时间复杂度O(nlog2的n次方) 空间复杂度 O(n)

​ 3.异或 时间复杂度O(n) 空间复杂度 O(1)

更改题目为:一组数据,其中有两个元素只出现一次,其他元素均出现两次,请找出只出现一次的元素

最优解决方法: 第一步:整体异或

​ 第二步:找到非0位

​ 第三步:根据非0位进行分组,分为两组

​ 第四步:各组异或 就得到了只出现一次的这两个元素

用代码进行实现,如下

#include <iostream>
using namespace std;void Find(int arr[]){int res1 = 0;for (int i : arr) {//全部异或一遍 获得两个只出现一次元素的异或的结果res1 ^= i;}unsigned int res2 = 1;//从右到左找到二进制上第一个为1的while (1) {//与1进行位于if (res1 & res2) {break;}res2 = res2 << 1;}int result1 = 0;int result2 = 0;for (int i : arr) {//遍历分类并对两组数进行异或得到结果if (res2 & i) {result1 ^= i;}else {result2 ^= i;}}cout << result1 << "   " << result2 << endl;
}
int main() {int nums[] = { 1,5,5,4,4,3 };//这里是测试样例Find(nums);return 0;
}

相关文章:

数据结构----结构--线性结构--顺序存储--数组

数据结构----结构–线性结构–顺序存储–数组 数组&#xff1a;类型相同&#xff0c;空间连续&#xff0c;长度固定 搜索&#xff1a; &#xff08;1&#xff09;基于索引搜索&#xff0c;时间复杂度O(1) &#xff08;2&#xff09;基于数值搜索&#xff1a; ​ 1.有序的&…...

docker 启动kitex 的opentelemetry

https://github.com/cloudwego/kitex-examples/blob/main/opentelemetry/docker-compose.yaml 下载两个yaml文件&#xff1a;docker-compose.yaml otel-collector-config.yaml 在该目录下执行 docker-compose up -d...

Excel中——日期列后添加星期

需求&#xff1a;在日期列中添加星期几&#xff1f; 第一步&#xff1a;打开需要添加星期的Excel文件&#xff0c;在日期后面添加日期 第二步&#xff1a;选择日期列&#xff0c;点击鼠标右键&#xff0c;在下拉列表中&#xff0c;选择“设置单元格格式” 第三步&#xff1a; 在…...

谈谈DNS是什么?它的作用以及工作流程

作者&#xff1a;Insist-- 个人主页&#xff1a;insist--个人主页 作者会持续更新网络知识和python基础知识&#xff0c;期待你的关注 目录 一、DNS是什么&#xff1f; 二、DNS的作用 三、DNS查询流程 1、查看浏览器缓存 2、查看系统缓存 3、查看路由器缓存 4、查看ISP …...

Qt小项目贪吃蛇实线,主要掌握定时器、信号与槽、按键事件、绘制事件、坐标运算、随机数生成等

Qt小项目贪吃蛇实线&#xff0c;主要掌握定时器、信号与槽、按键事件、绘制事件、坐标运算、随机数生成等 Qt 贪吃蛇演示QWidget 绘制界面项目源文件 注释清晰widget.hwidget.cpp 拓展QTimerQKeyEventQRectFQPointFQPainterQIcon Qt 贪吃蛇演示 QWidget 绘制界面 项目源文件 注…...

使用HTTP隧道时如何应对目标网站的反爬虫监测?

在进行网络抓取时&#xff0c;我们常常会遇到目标网站对反爬虫的监测和封禁。为了规避这些风险&#xff0c;使用代理IP成为一种常见的方法。然而&#xff0c;如何应对目标网站的反爬虫监测&#xff0c;既能保证数据的稳定性&#xff0c;又能确保抓取过程的安全性呢&#xff1f;…...

怎么样通过Bootstrap已经编译好(压缩好)的源码去查看符合阅读习惯的源码【通过Source Map(源映射)文件实现】

阅读本篇博文前&#xff0c;建议大家先看看下面这篇博文&#xff1a; https://blog.csdn.net/wenhao_ir/article/details/132089650 Bootstrap经编译(压缩)后的源码百度网盘下载地址&#xff1a; https://pan.baidu.com/s/14BM9gpC3K-LKxhyLGh4J9Q?pwdm02m Bootstrap未经编译…...

【排序算法】python之冒泡,选择,插入,快速,归并

参考资料&#xff1a; 《Python实现5大排序算法》《六大排序算法&#xff1a;插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序》 --代码似乎是C语言 ———————— 本文介绍5种常见的排序算法和基于Python实现&#xff1a; 冒泡排序&#xff08;Bubble Sort&am…...

UML—用例图的那些事

目录 背景: 1.用例图的发展史 过程: 1.用例图中的元素和关系 2.应用中的例子 总结&#xff1a; 背景: 1.用例图的发展史 用例图是一种常用的软件工程工具&#xff0c;用于描述系统的功能需求和用户与系统的交互。它在软件开发过程中起到了重要的作用&#xff0c;并且经历了…...

迷宫出口问题求解(DFS)

题面 一天Extense在森林里探险的时候不小心走入了一个迷宫&#xff0c;迷宫可以看成是由 nn 的格点组成&#xff0c;每个格点只有 22 种状态&#xff0c; 00 和 11&#xff0c;前者表示可以通行后者表示不能通行。 同时当Extense处在某个格点时&#xff0c;他只能移动到东南西北…...

基础算法模板

数据结构 单链表的插入删除 const int N=1e6+10; int head,e[N],ne[N],idx; //head 存储头节点的下标 //idx 存储当前已经用到的那个点 void init() {head=-1;idx=0; } void add_to_head(int x)//插入头节点操作 {e[idx]=x;ne[idx]=head;head=idx;idx++; } void add(int k)/…...

react Ref 的基本使用

类组件中使用ref 在类组件中&#xff0c;你可以使用createRef来创建一个ref&#xff0c;并将它附加到DOM元素或类组件实例上。使用ref允许你在类组件中访问和操作特定的DOM元素或类组件实例。 下面是在类组件中使用ref的步骤&#xff1a; 引入React和createRef&#xff1a; …...

宝塔面板点击SSL闪退打不开怎么解决?

宝塔Linux面板点击SSL证书闪退如何解决&#xff1f;旧版本的宝塔Linux面板确实存在这种情况&#xff0c;如何解决&#xff1f;升级你的宝塔Linux面板即可。新手站长分享宝塔面板SSL闪退的解决方法&#xff1a; 宝塔面板点击SSL证书闪退解决方法 问题&#xff1a;宝塔Linux面板…...

如何将安卓 Gradle 模块打包发布到本地 Maven 仓库

文章目录 具体流程 笔者的运行环境&#xff1a; Android Studio Flamingo | 2022.2.1 Android SDK 33 Gradle 8.0.1 JDK 17 Android 的 Gradle 项目与一般的 Gradle 项目是不同的&#xff0c;因此对将 Gradle 模块打包发布到本地 Maven 仓库来说&#xff0c;对普通 Gradle …...

【Docker】Docker比虚拟机快的原因、ubuntu容器、镜像的分层概念和私有库的详细讲解

&#x1f680;欢迎来到本文&#x1f680; &#x1f349;个人简介&#xff1a;陈童学哦&#xff0c;目前学习C/C、算法、Python、Java等方向&#xff0c;一个正在慢慢前行的普通人。 &#x1f3c0;系列专栏&#xff1a;陈童学的日记 &#x1f4a1;其他专栏&#xff1a;CSTL&…...

java.lang.IllegalArgumentException: Invalid character found in methodname

postman请求异常&#xff1a;java.lang.IllegalArgumentException: Invalid character found in method name. HTTP method names must be tokens...

【PCB专题】Allegro高速电路Xnet网络等长约束——SDIO信号为例

高速PCB板布线过程中,经常遇到等长设置问题,例如DDR的一组数据线和地址线等。但是由于数据线和地址线中间有一个电阻(或排阻),这种情况下设置等长就要引入Xnet的概念,通过设置Xnet的等长来确保数据线和地址线的等长。 由无源、分立器件(电阻、电容、电感)连接起来的几段…...

leetcode每日一练-第278题-第一个错误的版本

一、思路 二分查找——因为它可以快速地将版本范围缩小一半&#xff0c;从而更快地找到第一个坏版本。 二、解题方法 维护一个左边界 left 和一个右边界 right&#xff0c;在每一步循环中&#xff0c;我们计算中间版本 mid&#xff0c;然后检查它是否是坏版本。如果是坏版本…...

最小生成树笔记(Prim算法Kruskal算法)

1.最小生成树 最小生成树&#xff08;Minimum Spanning Tree&#xff0c;简称MST&#xff09;是指&#xff1a;在一个连通无向图中&#xff0c;找到一个包含所有顶点的树&#xff0c;且该树的所有边的权重之和最小。 换句话说&#xff0c;最小生成树是原图中的一个子图&#…...

4、数据清洗

4、数据清洗 前面我们处理的数据实际上都是已经被处理好的规整数据&#xff0c;但是在大数据整个生产过程中&#xff0c;需要先对数据进行数据清洗&#xff0c;将杂乱无章的数据整理为符合后面处理要求的规整数据。 数据去重 1.删除重复数据groupby().count()&#xff1a;可以…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...