数组¶

一、结构特性¶

基本定义：

数组是存放在连续内存空间上的相同类型数据的线性表结构

主要特点：

线性表数据结构
连续的内存空间
相同类型的数据

1.1 线性表结构¶

线性表的特点：

数据排成一条线一样的结构
数据最多只有前后两个方向

数据结构分类：

线性表：数组、链表、队列、栈
非线性表：树、堆、图

1.2 连续内存空间¶

数组元素之间没有空隙，是连续存储的
支持随机访问，时间复杂度是 O(1)
删除和插入慢，时间复杂度是 O(n)

问：为什么数组索引是从 0 开始？

答：因为索引的含义本质上是内存地址的偏移量，而第一个元素的偏移量就是 0。

1.3 相同类型数据¶

数组中保存的是同种类型的数据
每个元素占用的内存空间是一样的

正因为元素类型一样，占用空间相同，所以才能对数组进行随机访问。

二、常用操作¶

2.1 遍历¶

数组是连续的，遍历元素时，可通过索引偏移来实现

void traverse(int[] nums) {
    int n = nums.length;
    // 通过索引偏移遍历数组
    for (int i = 0; i < n; i++) {
        // 访问元素 nums[i]
    }
}

2.2 插入¶

数组是连续的，插入元素时，需将插入位置后面的元素都向后移动一位

void insert(int[] nums, int index, int value) {
    int n = nums.length;
    // 将 index 后面的元素都向后移动一位
    for (int i = n - 1; i >= index + 1; i--) {
        nums[i] = nums[i - 1];
    }
    // 插入元素
    nums[index] = value;
}

2.3 删除¶

数组是连续的，删除元素时，需将删除位置后面的元素都向前移动一位

void delete(int[] nums, int index) {
    int n = nums.length;
    // 将 index 后面的元素都向前移动一位
    for (int i = index; i < n - 1; i++) {
        nums[i] = nums[i + 1];
    }
}

2.4 查找¶

数组是连续的，查找元素时，可通过索引偏移来实现

int search(int[] nums, int target) {
    int n = nums.length;
    // 通过索引偏移遍历数组
    for (int i = 0; i < n; i++) {
        if (nums[i] == target) {
            return i;
        }
    }
    return -1;
}

2.5 扩容¶

数组大小是固定的，扩容时，需重新申请一块更大的空间，将原数组拷贝到新数组中

int[] resize(int[] nums) {
    int n = nums.length;
    // 申请更大的内存空间
    int[] newNums = new int[n * 2];
    // 将原数组元素拷贝到新数组中
    for (int i = 0; i < n; i++) {
        newNums[i] = nums[i];
    }
    return newNums;
}

三、注意事项¶

3.1 避免破坏数组连续性¶

连续性引起的问题：

删除会导致数组元素移动，多次删除，会引发数组移动多次，很影响性能

避免删除破坏连续性的可行方案：

先标记：删除数组元素时，仅标记被删除的元素，但是暂时先不要移动数组元素
再删除：等数组空间不足时，再触发真正的删除，一次性清除所有标记删除的元素

3.2 谨防数组访问越界¶

数组长度是有限的，避免访问数组以外的地方
数组以外的地方，有可能是其他程序的数据，越界修改有可能会影响其他程序运行

四、优缺点¶

4.1 优点¶

空间效率高：连续的内存空间，无额外开销
支持随机访问：允许在 O(1) 时间内访问元素
对缓存局部性友好：数组时连续的，能有效利用 CPU 缓存，提高性能
有序数组的二分查找：数组是连续的，可以使用二分查找

4.2 缺点¶

大小固定：数组是预先申请连续的内存空间，想要改变，只能重新申请新空间
低效的插入和删除：插入和删除需移动大量元素
空间浪费：分配空间远比使用的大时会浪费空间

五、适用场景¶

数据大小固定
随机访问元素
多维数组
算法要求性能高
底层框架开发，性能要求高

六、示例：容器¶

6.1 需求¶

数据量大小未知，需要动态扩容
一般业务需求，性能要求不高

6.2 特点¶

封装了数组操作的一些细节，比如增删
支持动态扩容，在空间不足时自动扩容

七、常用算法¶

排序（快速排序、归并排序等）
二分查找
双指针（快慢指针、前后指针）
滑动窗口
前缀和
哈希表
堆

参考¶

https://www.hello-algo.com/chapter_array_and_linkedlist/array/

https://time.geekbang.org/column/article/40961