概念

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

1
2
3
4
5
6
7

基本操作

索引

用数组下标找数组元素的过程

a[0];
a[9];
1
2

其中[]中的值必须为非负数，并且要小于数组的长度

时间复杂度为O(1)

查找

用数组元素找数组下标的过程

通过遍历整个数组的方式来查找，时间复杂度为O(n)

for(int i = 0; i<a.length; i++){
            if(i == target){
                System.out.println(i);
            }
        }
1
2
3
4
5

• 遍历这个数组
• 对数组元素与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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

删除

将数组的第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));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

相信大家都发现了，在插入和删除操作中，我都使用了构建新数组的方式来进行操作，Java中数组是固定长度的，无法直接进行操作

刷题巩固

增量元素之间的最大差值

俩数之和

数组形式的整数加法

674. 最长连续递增序列 - 力扣（LeetCode）