Web Lion

Appearance

数组（Array） ​

数组（Array） 是计算机科学中最基础的数据结构之一，它用连续的内存空间存储相同类型的元素，并通过**下标（索引）**快速访问元素。以下是关于数组的核心知识点：

一、基本概念 ​

  1. 定义

    • 数组是由相同数据类型的元素构成的集合，占用连续的内存空间。
    • 元素通过**下标（索引）**访问，下标通常从0开始（如第1个元素的下标为0）。

  2. 存储结构

    • 内存中，数组元素按顺序连续存放，每个元素占用固定大小的空间。
    • 例如，整数数组 [10, 20, 30] 在内存中的布局可能为：
      内存地址   值
0x1000    10
0x1004    20
0x1008    30
      （假设每个整数占4字节，地址递增4）。

  3. 维度

    • 一维数组：线性排列（如 [1, 2, 3]）。
    • 多维数组：数组的数组（如二维数组可视为“矩阵”）。

二、数组的操作与复杂度 ​

1. 访问元素 ​

  • 时间复杂度：O(1)（随机访问）。
  • 通过下标直接计算内存地址：address = base_address + index * element_size。
  • 示例：访问数组 a[2]，直接定位到内存地址 base + 2*size。

2. 插入元素 ​

  • 时间复杂度：O(n)（最坏情况，需移动后续元素）。
  • 示例：在数组 [1, 2, 3, 4] 的下标1处插入5，需将后续元素后移：
    原数组：[1, 2, 3, 4]
插入后：[1, 5, 2, 3, 4]  // 2、3、4后移

3. 删除元素 ​

  • 时间复杂度：O(n)（需移动后续元素填补空缺）。
  • 示例：删除数组 [1, 5, 2, 3, 4] 的下标1处元素，需将后续元素前移：
    原数组：[1, 5, 2, 3, 4]
删除后：[1, 2, 3, 4]     // 2、3、4前移

4. 遍历数组 ​

  • 时间复杂度：O(n)（需访问每个元素一次）。
  • 示例（Python）：
    python
    arr = [1, 2, 3, 4]
for element in arr:
    print(element)

三、静态数组 vs 动态数组 ​

1. 静态数组 ​

  • 特点：
    • 大小在创建时固定，无法动态调整；
    • 内存连续分配，空间利用率高。
  • 缺点：可能导致空间浪费（如预留过大）或溢出（如数据超过容量）。
  • 示例（C语言）：
    c
    int static_arr[5];  // 创建大小为5的静态数组

2. 动态数组 ​

  • 特点：
    • 大小可动态调整（如Java的ArrayList、Python的list）；
    • 底层通常基于静态数组实现，当容量不足时自动扩容（如翻倍）。
  • 扩容机制：
    1. 创建更大的新数组（如原容量的2倍）；
    2. 将原数组元素复制到新数组；
    3. 释放原数组内存。
  • 扩容时间复杂度：均摊O(1)（单次扩容代价高，但多次操作平均后接近O(1)）。
  • 示例（Python）：
    python
    dynamic_list = []  # 初始为空
dynamic_list.append(1)  # 动态添加元素
dynamic_list.append(2)

四、多维数组 ​

1. 二维数组（矩阵） ​

  • 定义：由行和列构成的表格状结构，可视为“数组的数组”。
  • 访问方式：array[row][column]。
  • 内存布局：
    • 行优先存储：先存储第一行，再存储第二行，以此类推（如C、Python）；
    • 列优先存储：先存储第一列，再存储第二列（如Fortran）。
  • 示例（Python）：
    python
    matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
print(matrix[1][2])  # 输出6（第2行第3列）

2. 多维数组 ​

  • 三维数组可视为“立方体”，四维及以上数组用于更复杂的数学模型。
  • 访问方式：array[i][j][k]（三维示例）。

五、数组的应用场景 ​

  1. 存储连续数据

    • 如图像像素（二维数组）、音频采样数据（一维数组）。

  2. 实现其他数据结构

    • 栈、队列、哈希表等可基于数组实现（如顺序栈）。

  3. 高效随机访问

    • 适用于需要快速定位元素的场景（如数据库索引）。

  4. 算法设计

    • 排序算法（如快速排序、归并排序）的主要操作对象；
    • 动态规划中常用数组存储中间结果。

六、常见数组操作的代码示例 ​

1. 创建与初始化 ​

python
# 一维数组
arr1 = [1, 2, 3, 4]

# 二维数组（3x3矩阵）
arr2 = [[0 for _ in range(3)] for _ in range(3)]
# 等价于：[[0, 0, 0], [0, 0, 0], [0, 0, 0]]

2. 插入元素 ​

python
arr = [1, 2, 3, 4]
arr.insert(1, 5)  # 在索引1处插入5
print(arr)  # 输出：[1, 5, 2, 3, 4]

3. 删除元素 ​

python
arr = [1, 5, 2, 3, 4]
arr.pop(1)  # 删除索引1处的元素
print(arr)  # 输出：[1, 2, 3, 4]

4. 遍历与修改 ​

python
arr = [1, 2, 3, 4]
for i in range(len(arr)):
    arr[i] *= 2  # 每个元素乘以2
print(arr)  # 输出：[2, 4, 6, 8]

七、数组的优缺点 ​

优点缺点
随机访问效率极高（O(1)）插入/删除效率低（O(n)）
内存连续，空间利用率高静态数组大小固定
实现简单动态数组扩容有性能开销

八、面试高频问题 ​

  1. 数组去重

    • 问题：移除数组中的重复元素。
    • 解法：排序后双指针遍历，或用哈希表（如Python的set）。

  2. 两数之和

    • 问题：在数组中找到两个数的和等于目标值。
    • 解法：哈希表记录已遍历元素，O(n)时间复杂度。

  3. 滑动窗口最大值

    • 问题：给定滑动窗口，求每个窗口中的最大值。
    • 解法：双端队列（维护窗口内的递减元素）。

  4. 螺旋矩阵

    • 问题：按螺旋顺序遍历二维矩阵。
    • 解法：模拟螺旋路径，逐层遍历。

数组是理解数据结构的基础，后续的栈、队列、哈希表等结构均基于数组实现。掌握数组的核心操作和复杂度分析是解决算法问题的关键。

Released under the MIT License.

Copyright © 2025-present Void Wind