七日算法先导（一）—— 数组

作者：秋名山码民

2022 年 8 月 01 日
本文字数：1371 字
阅读完需：约 4 分钟

概念

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));    }}