数组

一、数组的定义与结构

数组（Array）是一种用连续的内存空间存储相同数据类型数据的线性数据结构。

• 数组变量本身存储在栈内存中，指向堆内存中的数组首地址
• 数组的每个元素在堆内存中按顺序连续排列，地址连续且固定
• 例如 int[] array = {22,33,88,66,55,25};，变量 array 指向数组的首地址，通过下标可直接访问对应元素

---

二、数组的寻址原理

1. 寻址公式

数组元素的内存地址通过以下公式计算：

a[i] = baseAddress + i * dataTypeSize

• baseAddress：数组的首地址
• i：数组下标
• dataTypeSize：数组中元素类型的大小（如 int 类型为4个字节）

2. 为什么数组下标从0开始？

如果数组下标从1开始，寻址公式将变为：

a[i] = baseAddress + (i-1) * dataTypeSize

这会在每次访问元素时增加一次减法指令，增加CPU运算开销，因此下标从0开始的设计能最大化提升寻址效率。

---

三、数组操作的时间复杂度

1. 查找操作

• 随机查询（通过下标查询）： 直接通过寻址公式计算内存地址，时间复杂度为 O(1)。

  public int getElement(int[] a, int i) {
      return a[i];
  }

• 未知索引查询（无序数组）： 需要遍历数组逐个比对，时间复杂度为 O(n)。
• 未知索引查询（有序数组）： 可通过二分查找优化，时间复杂度为 O(logn)。

2. 插入与删除操作

数组是连续内存结构，为保证内存连续性，插入或删除元素时需要移动后续元素：

• 最好情况（在数组末尾操作）：无需移动元素，时间复杂度为 O(1)
• 最坏情况（在数组开头操作）：需要移动所有元素，时间复杂度为 O(n)
• 平均情况：时间复杂度为 O(n)

---

四、面试相关问题

1. 问：数组的定义是什么？它的底层存储结构有什么特点？答： 数组是一种用连续的内存空间存储相同数据类型数据的线性数据结构。它的底层存储特点是：数组变量指向堆内存中的数组首地址，元素在堆内存中按顺序连续排列，地址固定且连续。

2. 问：为什么数组的下标从0开始，而不是从1开始？答： 数组下标从0开始是为了优化寻址效率。数组元素的寻址公式为 a[i] = baseAddress + i * dataTypeSize，如果下标从1开始，公式需要变为 a[i] = baseAddress + (i-1) * dataTypeSize，每次访问元素都需要额外执行一次减法运算，增加CPU开销，因此从0开始的设计更高效。

3. 问：数组的查找、插入、删除操作的时间复杂度分别是多少？答：

   • 查找：通过下标随机查询的时间复杂度为O(1)；无序数组未知索引查询为O(n)；有序数组二分查找为O(logn)。
   • 插入/删除：最好情况（末尾操作）为O(1)，最坏情况（开头操作）为O(n)，平均时间复杂度为O(n)。

4. 问：为什么数组的插入和删除操作效率较低？答： 因为数组是连续的内存结构，为了保证内存连续性，在插入或删除元素时，需要移动后续所有元素，导致操作效率较低，平均时间复杂度为O(n)。