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

数据结构——数组

数组定义:

 在计算机科学中,数组是由一组元素(值或变量)组成的数据结构,每个元素有至少一个索引或键来标识。

因为数组内的元素是连续存储的,所以数组中元素的地址,可以通过其索引计算出来。

性能空间占用

java中所有对象的大小都是8字节的整数倍,不足的要用对齐字节补足

随机访问

即根据索引查找元素,时间复杂度是O(1)

动态数组
 private int size; // 逻辑大小private int capacity=8; // 容量private int[] array=new int[capacity];
插入
//向最后的位置[size]添加元素public void addLast(int element){array[size]=element;size++;}
//向[0....size]位置添加元素public void add(int index,int element){//未考虑数组扩容问题if(size>=0&&index<size) {//进行一个拷贝System.arraycopy(array, index, array, index + 1, size - index);array[index] = element;size++;} else if(index==size){//addLastarray[index]=element;size++;}}

public void add1(int index,int element){if(size >= 0 && index < size){System.arraycopy(array,index,array,index+1,size-index);}array[index]=element;size++;}
查询和遍历元素
//查询元素public int get(int index){//[0....size]return array[index];}//打印每个元素public void foreach(){for (int i=0;i<size;i++){System.out.println(array[i]);}}//函数式接口//遍历方法1,consumer接口 遍历执行的操作,每个元素入参public void foreach1(Consumer<Integer> consumer){for(int i=0;i<size;i++){consumer.accept(array[i]);}}//Iterator 是个接口,要有实现类//迭代器遍历@Overridepublic Iterator<Integer> iterator() {//java里叫匿名内部类return new Iterator<Integer>() {int i=0;@Overridepublic boolean hasNext() {//有没有下一个严肃return i<size;}@Overridepublic Integer next() {//返回当前元素,并移动到下一个元素return array[i++];}};}public IntStream stream(){//IntStream 传的数字不仅有有效数字,还有无效的 eg:1,2,3,4,0,0,0,0return IntStream.of(Arrays.copyOfRange(array,0,size));}
  public static void main(String[] args) {System.out.println("Hello world!");DynamicArray dynamicArray = new DynamicArray();dynamicArray.addLast(1);dynamicArray.addLast(2);dynamicArray.addLast(3);dynamicArray.addLast(4);dynamicArray.add(2,5);for(int i=0;i<5;i++){System.out.println(dynamicArray.get(i));}//迭代器遍历for(Integer element:dynamicArray){//hasnext()、next()方法System.out.println(element);}}
删除
 public int remove(int index){  //[0...size]int removed=array[index];if(index<size-1) {//java数组中移动元素的方法System.arraycopy(array, index + 1, array, index, size - index - 1);}size--;return removed;}

对比数据是否一致(断言)

assertEquals(3,removed);

assertIterable(List.of(1,2,4,5),dynamicArray);

容量不够,先扩容
   private void checkAndGrow() {//容量检查if(size==0){array=new int[capacity];}if(size==capacity){//进行扩容,1.5   1.618   2capacity+=capacity>>1;int [] newArray=new int[capacity];System.arraycopy(array,0,newArray,0,size);array=newArray;}}

插入或删除性能

头部位置,时间复杂度是O(n)

中间位置,时间复杂度是O(n)

尾部位置,时间复杂度是O(1)

全部代码

package org.example;import java.util.Iterator;
import java.util.Arrays;
import java.util.function.Consumer;
import java.util.stream.IntStream;//动态数组
public class DynamicArray implements Iterable<Integer>{private int size; // 逻辑大小private int capacity=8; // 容量// private int[] array=new int[capacity];private int[] array={};//向最后的位置[size]添加元素public void addLast(int element){array[size]=element;size++;}//向[0....size]位置添加元素public void add(int index,int element){checkAndGrow();//未考虑数组扩容问题if(size>=0&&index<size) {//进行一个拷贝System.arraycopy(array, index, array, index + 1, size - index);array[index] = element;size++;} else if(index==size){//addLastarray[index]=element;size++;}}private void checkAndGrow() {//容量检查if(size==0){array=new int[capacity];}if(size==capacity){//进行扩容,1.5   1.618   2capacity+=capacity>>1;int [] newArray=new int[capacity];System.arraycopy(array,0,newArray,0,size);array=newArray;}}public void add1(int index,int element){if(size >= 0 && index < size){System.arraycopy(array,index,array,index+1,size-index);}array[index]=element;size++;}//查询元素public int get(int index){//[0....size]return array[index];}//打印每个元素public void foreach(){for (int i=0;i<size;i++){System.out.println(array[i]);}}//函数式接口//遍历方法1,consumer接口 遍历执行的操作,每个元素入参public void foreach1(Consumer<Integer> consumer){for(int i=0;i<size;i++){consumer.accept(array[i]);}}//Iterator 是个接口,要有实现类//迭代器遍历@Overridepublic Iterator<Integer> iterator() {//java里叫匿名内部类return new Iterator<Integer>() {int i=0;@Overridepublic boolean hasNext() {//有没有下一个严肃return i<size;}@Overridepublic Integer next() {//返回当前元素,并移动到下一个元素return array[i++];}};}public IntStream stream(){//IntStream 传的数字不仅有有效数字,还有无效的 eg:1,2,3,4,0,0,0,0return IntStream.of(Arrays.copyOfRange(array,0,size));}public int remove(int index){  //[0...size]int removed=array[index];if(index<size-1) {//java数组中移动元素的方法System.arraycopy(array, index + 1, array, index, size - index - 1);}size--;return removed;}}
二维数组

从行开始遍历比从列开始遍历更快。

局部性原理:(空间方面)

  cpu读取内存(速度慢)数据后,会将其放入高速缓存(速度快)中当中,如果后来的计算机再用到此数据,在缓存中能读到的话,就不必读内存了。

  缓存的最小存储单位是缓存行,一般是64bytes,一次读的数据少了不划算,因此最少读64bytes填满一个缓存行,因此读入某一个数据时也会读取其临近的数据,这就是所谓的空间局部性。

相关文章:

数据结构——数组

数组定义&#xff1a; 在计算机科学中&#xff0c;数组是由一组元素&#xff08;值或变量&#xff09;组成的数据结构&#xff0c;每个元素有至少一个索引或键来标识。 因为数组内的元素是连续存储的&#xff0c;所以数组中元素的地址&#xff0c;可以通过其索引计算出来。 性…...

python asyncio websockets server

python websocket server在收到接受消息处理完后会默认关闭连接。需要在msg_handler里面加个while true就能一直保持连接了。 start_server websockets.serve(msg_handler, "0.0.0.0", 29967) asyncio.get_event_loop().run_until_complete(start_server) asyncio.…...

视频素材免费网站有哪些?8个视频素材库网站下载推荐

在视频创作领域&#xff0c;选择正确的高质量无水印素材网站能够极大地丰富您的作品&#xff0c;让每一帧都鲜活起来。下面&#xff0c;我们继续为您介绍更多优质的视频素材网站&#xff0c;每一个都是您创作旅程中的宝贵资源。 1. 蛙学府&#xff08;中国&#xff09; 集合了…...

ChatGPT与传统搜索引擎的区别:智能对话与关键词匹配的差异

引言 随着互联网的快速发展&#xff0c;信息的获取变得比以往任何时候都更加便捷。在数字化时代&#xff0c;人们对于获取准确、及时信息的需求愈发迫切。传统搜索引擎通过关键词匹配的方式为用户提供了大量的信息&#xff0c;然而&#xff0c;这种机械式的检索方式有时候并不…...

xargs后调用bash自定义函数(写该函数文本到脚本, 并引导PATH)

xargs后调用bash自定义函数 需要3步骤,如下 function to_markdown_href_func() { fp$1 #echo $fpecho -e "\n[${fp}](${PREFIX}/${fp})" }BIN/tmp/bin/ F$BIN/to_markdown_href_func.sh mkdir -p $BIN 获得函数to_markdown_href_func的文本 ,写文本到 /tmp/bin/to_ma…...

学术论文写作新利器:ChatGPT技巧详解

ChatGPT无限次数:点击直达 学术论文写作新利器&#xff1a;ChatGPT技巧详解 在如今信息爆炸的时代&#xff0c;学术论文写作变得愈发重要且具有挑战性。随着人工智能技术的不断发展&#xff0c;ChatGPT作为一种强大的写作辅助工具&#xff0c;为学术论文创作者提供了全新的可能…...

Spring整合JDBC

1、引入依赖 <properties><maven.compiler.source>8</maven.compiler.source><maven.compiler.target>8</maven.compiler.target><project.build.sourceEncoding>UTF-8</project.build.sourceEncoding></properties><depen…...

详解Qt中的布局管理器

Qt中的布局管理是用于组织用户界面中控件&#xff08;如按钮、文本框、标签等&#xff09;位置和尺寸调整的一种机制。说白了就是创建了一种规则&#xff0c;随着窗口变化其中的控件大小位置跟着变化。Qt提供了多种布局管理器&#xff0c;每种都有其特定用途和特点。以下是对Qt…...

MyBatis 参数重复打印的bug

现象 最近有个需求&#xff0c;需要在mybatis对数据库进行写入操作的时候&#xff0c;根据条件对对象中的某个值进行置空&#xff0c;然后再进行写入&#xff0c;这样数据库中的值就会为空了。 根据网上查看的资料&#xff0c;选择在 StatementHandler 类执行 update 的时候进…...

ES6学习之路:迭代器Iterator和生成器Generator

迭代器 一、知识背景 什么是迭代器 迭代器就是在一个数据集合中不断取出数据的过程迭代和遍历的区别 遍历是把所有数据都取出迭代器注重的是依次取出数据&#xff0c;它不会在意有多少数据&#xff0c;也不会保证能够取出多少或者能够把数据都取完。比如斐波那契额数列&#…...

如何使用 DynamiCrafter Interp Loop 无缝连接两张照片

DynamiCrafter Interp Loop 是一个基于 AI 的工具&#xff0c;可以用来无缝连接两张照片。它使用深度学习技术来生成中间帧&#xff0c;从而使两张照片之间的过渡更加自然流畅。 使用步骤 访问 DynamiCrafter Interp Loop 网站&#xff1a;https://huggingface.co/spaces/Dou…...

今天起,Windows可以一键召唤GPT-4了

ChatGPT狂飙160天&#xff0c;世界已经不是之前的样子。 新建了人工智能中文站https://ai.weoknow.com 每天给大家更新可用的国内可用chatGPT资源 发布在https://it.weoknow.com 更多资源欢迎关注 微软 AI 大计的最后一块拼图完成了&#xff1f; 把 Copilot 按钮放在 Window…...

使用Kaggle API快速下载Kaggle数据集

前言 在使用Kaggle网站下载数据集时&#xff0c;直接在网页上点击下载可能会很慢&#xff0c;甚至会出现下载失败的情况。本文将介绍如何使用Kaggle API快速下载数据集。 具体步骤 安装Kaggle API包 在终端中输入以下命令来安装Kaggle API相关的包&#xff1a; pip install…...

java 通过 microsoft graph 调用outlook(二)

这次提供一些基础调用方式API PS&#xff1a; getMailFolders 接口返回的属性中&#xff0c;包含了未读邮件数量unreadItemCount 一 POM文件 <!-- office 365 --><dependency><groupId>com.google.guava</groupId><artifactId>guava<…...

【机器学习】代价函数

&#x1f388;个人主页&#xff1a;豌豆射手^ &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;机器学习 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共同学习、交流进…...

[leetcode] 100. 相同的树

给你两棵二叉树的根节点 p 和 q &#xff0c;编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同&#xff0c;并且节点具有相同的值&#xff0c;则认为它们是相同的。 示例 1&#xff1a; 输入&#xff1a;p [1,2,3], q [1,2,3] 输出&#xff1a;true示例 2&a…...

08、Lua 函数

Lua 函数 Lua 函数Lua函数主要有两种用途函数定义解析&#xff1a;optional_function_scopefunction_nameargument1, argument2, argument3..., argumentnfunction_bodyresult_params_comma_separated 范例 : 定义一个函数 max()Lua 中函数可以作为参数传递给函数多返回值Lua函…...

【数据分析面试】1. 计算年度收入百分比(SQL)

题目 你需要为公司的营收来源生成一份年度报告。计算截止目前为止&#xff0c;在表格中记录的第一年和最后一年所创造的总收入百分比。将百分比四舍五入到两位小数。 示例&#xff1a; 输入&#xff1a; annual_payments 表 列名类型amountINTEGERcreated_atDATETIMEstatusV…...

数据库SQL语句速查手册

SQL 语句语法AND / ORSELECT column_name(s) FROM table_name WHERE condition AND|OR conditionALTER TABLEALTER TABLE table_name ADD column_name datatypeorALTER TABLE table_name DROP COLUMN column_nameAS (alias)SELECT column_name AS column_alias FROM table_name…...

智慧城市一屏统览,数字孪生综合治理

现代城市作为一个复杂系统&#xff0c;牵一发而动全身&#xff0c;城市化进程中产生新的矛盾和社会问题都会影响整个城市系统的正常运转。智慧城市是应对这些问题的策略之一。城市工作要树立系统思维&#xff0c;从构成城市诸多要素、结构、功能等方面入手&#xff0c;系统推进…...

Python读取PDF文字转txt,解决分栏识别问题,能读两栏

搜索了一下&#xff0c;大致有这些库能将PDF转txt 1. PyPDF/PyPDF2&#xff08;截止2024.03.28这两个已经合并成了一个&#xff09;pypdf PyPI 2. pdfplumber GitHub - jsvine/pdfplumber: Plumb a PDF for detailed information about each char, rectangle, line, et cete…...

微信支付平台与微信服务号关联配置要点

目录 JSAPI支付 前期资料及相关准备 申请微信服务号 服务号配置要点 微信认证 基本配置 功能设置 申请微信支付号 支付号配置要点 设置操作密码 API安全 开发设置 与服务号关联 小结 JSAPI支付 我们的开发应用场景以JSAPI支付为举例&#xff0c;这也是常用的一…...

C++类复习

C类 1. 类内成员函数隐式声明为inline class Str {int x;int y 3; public:inline void fun(){std::cout<<"pf,yes!"<<std::endl;} };这段代码不会报错&#xff0c;但是类内的成员函数隐式声明为inline函数&#xff0c;不需要单独写在前面。因此将成员…...

Spring使用(一)注解

Spring使用 资源 Spring 框架内部使用 Resource 接口作为所有资源的抽象和访问接口&#xff0c;在上一篇文章的示例代码中的配置文件是通过ClassPathResource 进行封装的&#xff0c;ClassPathResource 是 Resource 的一个特定类型的实现&#xff0c;代表的是位于 classpath …...

Linux基本指令篇

在前边&#xff0c;我们已经了解过了Linux操作系统的发展和应用&#xff0c;从该篇起&#xff0c;就正式进入对Linux的学习。 今天我们就来在Xshell上远程登录我们的云服务器。首先我们要知道自己云服务器的公网ip&#xff0c;然后修改一下密码。 点击跳转 修改完密码之后我们…...

CSS实现小车旅行动画实现

小车旅行动画实现 效果展示 CSS 知识点 灵活使用 background 属性下的 repeating-linear-gradient 实现路面效果灵活运用 animation 属性与 transform 实现小车和其他元素的动画效果 动画场景分析 从效果图可以看出需要实现此动画的话&#xff0c;需要position属性控制元素…...

6_相机坐标系_相机4个坐标系详述

相机系列文章是用来记录使用opencv3来完成单目相机和6轴机械臂手眼标定。本人吃饭的主职是linux下6轴机械臂相关应用开发。但对于机械臂运动学、相机应用等都非常感兴趣&#xff0c;所以对一些线性代数基础薄弱又想深入了解机械臂内部运算的同志比较有体会。由于是探索性学习&a…...

软考 - 系统架构设计师 - 敏捷开发方法

前言 敏捷开发方法是一种以人为核心、迭代、循序渐进的软件开发方法。它强调团队合作、客户需求和适应变化&#xff0c;旨在通过快速迭代和反馈来快速交付高质量的软件产品。 敏捷开发方法的优势在于能够快速响应变化、提高开发效率和质量、增强团队协作和沟通&#xff0c;并降…...

Django 仿博客园练习

数据库搭建 部分功能介绍 【一】注册 &#xff08;1&#xff09;效果显示、简单简介 主要亮点 结合了layui和forms组件默认头像可以随着性别的选择发生改变自定义头像可以实时更新显示forms组件报错信息可以局部刷新显示在对应框体下面 没有直接使用layui的前端验证后端验证…...

MySQL(常用函数、多表查询)

文章目录 1.数据库函数1.count函数案例答案count&#xff08;*&#xff09;与count&#xff08;列&#xff09;的区别 2.sum函数案例答案 3.avg函数案例答案 4.max/min函数案例答案 5.group by 分组统计案例答案 6.字符串相关函数演示练习 7.数学相关函数演示 8.日期相关函数演…...

以下不属于专用网页制作工具的是/裤子seo标题优化关键词

文件搜索命令locate&#xff1a;搜索快&#xff0c;新建文件无法搜索&#xff1b;命令格式&#xff1a; locate 文件名 //在后台数据库中按文件名搜索&#xff0c;搜索速度快&#xff1b;/var/lib/mlocate: locate命令所搜索的后台数据库命令&#xff1a;updatedb // 更新数据…...

织梦网站栏目字体怎么调/域名注册要多少钱

HSQLDB 的研究与性能测试(与Mysql对比) 1. HSQLDB 简介 HSQLDB 数据库是一款纯 Java 编写的免费数据库&#xff0c;许可是 BSD-style 的协议。相对其他数据库来说&#xff0c;其体积小&#xff0c;才 563kb 。仅一个 hsqldb.jar 文件就包括了数据库引擎&#xff0c;数据库驱动&…...

中国人在俄罗斯做网站需要多少卢布/网店运营推广

简介 这里主要介绍PaddleClas中已经开源的常用系列模型&#xff0c;PaddleClas的github repo&#xff1a;https://github.com/PaddlePaddle/PaddleClas。PaddleClas中包含了ResNet、HRNet、Inception、Res2Net等系列模型&#xff0c;这篇博客主要是介绍其主要系列模型。AlexNe…...

wordpress火车头采集免费版/吉林黄页电话查询

好程序员java分享Java面试宝典&#xff1a;类的加载过程&#xff0c;类加载过程主要包含加载、验证、准备、解析、初始化、使用、卸载七个方面&#xff0c;下面一一阐述。 一、加载 在加载阶段&#xff0c;虚拟机主要完成三件事&#xff1a; 1.通过一个类的全限定名来获取定义此…...

学生做网站怎么收费/郑州seo方案

话题一&#xff1a;异或先看一段代码吧&#xff1a;这段代码是用来实现a,b交换的。异或是位运算符&#xff0c;0^1为1&#xff0c;其他情况都是0&#xff0c;这是一个加法不进位的功能&#xff01;这有什么用呢&#xff1f;其实通过上面交换的例子&#xff0c;我们已经明白A^B^…...

济南地区做公司网站的公司/中国十大软件外包公司

tabBar 的属性配置 官方文档链接https://uniapp.dcloud.io/collocation/pages?idtabbar 在page.json中配置 例如&#xff1a; {"pages": [ //pages数组中第一项表示应用启动页&#xff0c;参考&#xff1a;https://uniapp.dcloud.io/collocation/pages{"pa…...