算法入门之数组简介

数组简介

什么是数组

数组是算法中最简单、最常用的线性结构，那么数组的定义是什么呢？

首先是一片连续的空间，用来存放有限个相同类型的数据集合，这就称为数组。

数组的基本操作

基本操作无外乎增删改查，其中查和改是最简单的，因为数组是一片连续的空间，访问数组中的元素可以通过数组的下标直接访问，这里需要注意数组的下标是从0开始，数组下标的最大值为数组长度-1，如果超出将抛出异常提示数组下标越界。

查询元素

// 定义数组（定义方式有多种，不详细介绍）
int[] arr = new int[]{1,3,5,2,4,9};
// 查询数据下标为4的元素
System.out.println(arr[4]);

1
2
3
4
5

修改元素

int[] arr = new int[]{1,3,5,2,4,9};
System.out.println(Arrays.toString(arr));

// 修改下标为4的元素为10
arr[4] = 10;
System.out.println(Arrays.toString(arr));

1
2
3
4
5
6
7

这两个操作时间复杂度都是O(1)，那么我们来看看剩余的两个。

插入元素

插入元素需要讨论如下三种情况

• 超范围插入。

• 插入元素位于中间时需要将部分元素从左往右移动一个单元，才能插入。

• 插入元素位于对尾，这就很简单类似于元素修改。

示意图如下

/***
 * 自定义数组
 */
class MyArray {
    // 数组实际元素个数
    private int size;
    private int[] arr;

    public MyArray(int capacity){
        this.size = 0;
        this.arr = new int[capacity];
    }

    /**
     * 插入元素
     * @param index 插入位置下标
     * @param date 插入数据
     */
    public void insert(int index,int date){
        /**
         * 判断数组下标是否小于0，因为数组下标必须为0或者正整数
         */
        if (index < 0 || index > size){
            throw new RuntimeException("数组下标有误");
        }

        /**
         * 从数组中间插入，需要将[index,size]之间的数组从左往右移动一个数组下标
         */
        for (int i = size; i > index; i--) {
            arr[i+1] = arr[i];
        }
        arr[index] = date;
        size++;
    }

    public void show(){
        System.out.println(Arrays.toString(arr));
    }
}

public class ArrayDemo {
    public static void main(String[] args) {
        MyArray myArray = new MyArray(8);
        myArray.insert(0,1);
        myArray.insert(1,3);
        myArray.insert(2,5);
        myArray.insert(3,2);
        myArray.insert(4,4);
        myArray.insert(5,9);

        myArray.insert(4,10);

        myArray.show();
    }
}

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

但是这种方式插入就会遇到一个问题，当我们不断插入数组的size等于了capacity，那么数组需要怎么处理呢？这就需要用到扩容，将数组容量扩大一倍后再去操作，这就是上面提到的超范围插入，代码改造如下

// 插入时加入容量判断，容量不够直接扩容为之前的两倍
if (size >= arr.length){
    System.out.println("要扩容了~");
    int[] newArr = new int[arr.length * 2];
    System.arraycopy(arr,0,newArr,0,arr.length);
    arr = newArr;
    System.out.println("扩容结束~");
}

1
2
3
4
5
6
7
8
9

插入元素可能涉及到两个动作，数组移动和扩容，这两个动作时间复杂度都是O(n)，那么插入元素整个复杂度还是为O(n)。

删除元素

删除元素和插入元素类似，如果是中间插入元素那么区间[index,size]的元素需要从左往右移动，而删除是从右往左移动。

public int delete(int index){
    if (index < 0 || index > size){
        throw new RuntimeException("数组下标有误");
    }

    int deleteElement = arr[index];

    for (int i = index; i