七日算法先导(一)—— 数组
2023-02-18 16:27:09 时间
概念
1. 顺序存储
顺序存储结构,指用一段地址连续的存储单元依次存储线性表的数据元素
2. 存储方式
第一个元素存储到下标为0 的位置中,第二个元素存储到下标为1的位置中,以此类推
3. 长度和容量
数组的长度指代的是数组中当前有多少个元素,数组的容量指代的是数组中MAX存储多少个元素
注意数组越界的问题,Java中的数组是固定长度
如何获取数组长度,以Java语言为例:
public class Main {
public static void main(String[] args) {
int[] a = new int[10];
System.out.println(a.length);//数组长度为10
}
}
基本操作
索引
用数组下标找数组元素的过程
a[0];
a[9];
其中[]中的值必须为非负数,并且要小于数组的长度
时间复杂度为O(1)
查找
用数组元素找数组下标的过程
通过遍历整个数组的方式来查找,时间复杂度为O(n)
for(int i = 0; i<a.length; i++){
if(i == target){
System.out.println(i);
}
}
- 遍历这个数组
- 对数组元素与target进行比较,人工相等返回对应数据的下标
- 当i>a.length时候,还找不到,表明数组中不存在这个元素,直接返回-1
插入
在第k个元素前进行插入一个数,由于数组是连续的,那么从k个元素往后的元素都必须往后移动一位,当k=0时,所有元素都要往后移动,所以最坏时间复杂度为O(n)
public static int[] insert(int[] arr,int i,int I){
//新建数组对原数组扩容
int[] arr1 = new int[arr.length+1];
//将arr中的元素赋值给arr
for(int j = 0; j<arr.length; j++){
arr1[j] = arr[j];
}
//将大于i的数据向后移动一位
for(int j = arr1.length -1; j>i;j--){
arr1[j+1] = arr[j];
}
//进行赋值
arr1[i+1] = I;
return arr1;
}
删除
将数组的第k个元素删除,由于数组是连续的,那么第k个元素删除,往后的元素势必要往前移动一位,当k = 0时候,所有元素都要往前移动,所有最坏时间复杂度为O(n)
public class Demo {
public static void main(String[] args) {
int[] oldarray = new int[] {3, 4, 5, 6, 7};// 原始数组
int num = 2; // 删除索引为 2 的元素,即删除第三个元素 5
int[] newArray = new int[oldarray.length-1];// 新数组,长度为原始数组减去 1
for(int i=0;i<newArray.length; i++) {
// 判断元素是否越界
if (num < 0 || num >= oldarray.length) {
throw new RuntimeException("元素越界... ");
}
//
if(i<num) {
newArray[i] = oldarray[i];
}
else {
newArray[i] = oldarray[i+1];
}
}
// 打印输出数组内容
System.out.println(Arrays.toString(oldarray));
oldarray = newArray;
System.out.println(Arrays.toString(oldarray));
}
}
相信大家都发现了,在插入和删除操作中,我都使用了构建新数组的方式来进行操作,Java中数组是固定长度的,无法直接进行操作
刷题巩固
相关文章
- Kotlin/Java 读取Jar文件里的指定文件
- 极路由4增强版B70(HC5962)刷机
- 当 xxl-job 遇上 docker → 它晕了,但我不能乱!
- RHCE环境准备 | 介绍
- 登云之路|腾讯大规模云原生技术实践案例图鉴
- 我做了一款vscode主题! Dapanna Theme
- 第一周好文分享(强推这个系列!)
- canvas详细教程! ( 近1万字吐血总结)
- canvas绘制动画原理及案例讲解(绘制小恐龙动画、时钟等)
- 纯Canvas绘制绘制小恐龙向前冲游戏(Vue3版本的升级版)
- 关于css的八个结构伪类选择器 :last-child、:first-of-type、:nth-last-of-type()
- 核酸码系统拆解与设计推演
- 从零开始的内存马分析——如何骑马反杀(二)
- 从零开始的内存马分析——如何骑马反杀(三)
- 神兵利器|网络资产测绘平台聚合工具(AsamF)
- Hadoop3.0-Hdfs | Apache Hadoop介绍
- 记一次对HTB:Timelapse的渗透测试
- Ansible环境部署 | 概述
- Veinmind 在 Jenkins 的0部署成本自动化扫描方案
- 攻防|记一次攻防演练实战总结