数组总结

标签: 总结, 数组

集合、列表、数组

1. 集合

1. 特点：
   1. 唯一性：集合里的元素不会有重复；
   2. 无序性：集合里的元素顺序可以是乱序的；
2. 应用：
   1. 可用作「去重」

2. 列表

1. 特点：
   1. 有序
   2. 长度可变
   3. 是在「集合」的特征上形成的
   4. 列表中的元素，在内存中可能彼此相邻，也可能不相邻
2. 表现形式：
   1. 数组
   2. 链表
   3. 栈
   4. 队列

3. 数组

1. 特点：
   1. 数组有「索引」，列表没有「索引」
   2. 数组元素在内存中，是连续存储的，且每个元素占用相同大小的内存。

数组常用操作

1. 读取元素

1. 初始化时，计算机会为数组申请「一段连续的空间」，并记录下「索引为 0 的内存地址」
2. 当要访问索引为 n 的元素时，会进行以下计算：
   1. 找到「索引为 0 的内存地址」
   2. 返回「内存地址 + n」，作为目标元素的地址。
3. 时间复杂度：O(1)

2. 查找元素

1. 从索引为 0 的元素依次向后查找，直到找到目标元素，或者遍历结束后找不到目标元素
2. 时间复杂度：O(n)

3. 插入元素

1. 插入到末尾：
   1. 通过「数组长度」和「数组的内存地址」计算出「即将插入元素的内存地址」，将元素插入即可。
2. 插入到其他位置：
   1. 腾出空间：将待插入位置后的元素，向后挪动，为带插入的元素腾出空间
   2. 插入：再将带插入元素插入

3. 频繁对数组进行插入操作会造成时间浪费，链表 这一数据结构的插入操作则快捷很多。

4. 时间复杂度：O(n)

4. 删除

1. 与插入元素类似：
   1. 删除目标元素
   2. 将数组中该元素之后的元素，依次 填补 到前一个元素的位置中。
2. 时间复杂度：O(n)

相关题目

No	Problem	Difficulty	Link	Solution	Comment
56	合并区间	中等	题目	题解	数组遍历
394	字符串解码	中等	题目	题解	数组和栈的使用
498	对角线遍历	中等	题目	题解	矩阵的遍历