01、数组
大约 16 分钟数据结构算法基础面试题解析数组程序厨校招社招
哈喽大家好，我是厨子，今天给大家介绍一下数组
数组是编程中最基础、最重要的数据结构之一，无论你使用哪种编程语言，都离不开数组的使用。
本文将带你深入理解数组的方方面面，从最基础的概念到高级应用，让你真正掌握这个强大的数据结构。
什么是数组？
咱们先来了解一下什么是数组？
数组（Array）是一种线性数据结构，它用来存储相同类型的数据元素。这些元素在内存中连续存储，并通过索引（下标）来访问。注意这里和链表的区别哦，面试时总会问链表和数组的特点，可以往内存上靠一下哈
简单来说，数组就像是一个有编号的储物柜，每个柜子里存放相同类型的物品，你可以通过柜子的编号快速找到并取出你要的物品。
)
数组在计算机中的作用
各位同学加入训练营的时候，导师应该给大家说了，学习技术时，对每一个出现的特性，都要主动探究其设计初衷，弄清楚这些特性是为了应对哪些具体问题而诞生的，去思考它们的应用场景
那么数组的应用场景有哪些呢？
- 存储批量数据：如学生成绩、商品价格、像素颜色值
- 快速访问数据：通过索引直接定位，不需要逐个查找（可当做哈希表使用，key 为索引，value 为具体值）
- 节省内存：连续存储，减少内存碎片
- 提高效率：许多算法都基于数组实现
下面我们来说一下面试时经常被问到的问题吧
数组的基本特性
连续存储空间
数组最重要的特性就是元素在内存中连续存储。
内存地址: 1000 1004 1008 1012 1016
数组元素: [10] [20] [30] [40] [50]
索引: 0 1 2 3 4
注意看上面的内容，地址是连续的
这种连续存储带来的好处：
- 快速访问：知道首地址和索引，可以直接计算任意元素的地址（目标元素地址 = 首地址 + 索引 × 单个元素大小）
- 缓存友好：访问相邻元素时，CPU缓存命中率高
- 内存效率：没有额外的指针开销
相同数据类型
数组中的所有元素必须是相同的数据类型：
// 正确的数组定义
int numbers[5] = {1, 2, 3, 4, 5}; // 整数数组
double prices[3] = {9.99, 15.5, 23.0}; // 浮点数组
char letters[4] = {'a', 'b', 'c', 'd'}; // 字符数组
// 错误：不能混合不同类型
// int mixed[] = {1, 2.5, 'a'}; // 编译错误
为什么要求相同类型？
- 内存计算：知道每个元素占用多少字节，才能准确计算地址（挺多同学应该忽略了这一点）
- 类型安全：编译器可以进行类型检查，避免错误
- 操作一致：对所有元素可以进行相同的操作
固定大小（静态数组）
静态数组在创建时就确定了大小，之后不能改变：
int scores[10]; // 创建一个能存储10个整数的数组
// 大小固定为10，不能变成11或9
固定大小的特点：
- 优点：内存分配简单，访问效率高
- 缺点：不够灵活，可能造成浪费或不够用
索引访问机制
数组使用索引（下标）来访问元素，C++ 使用0作为起始索引(这里又衍生出一个面试题了,数组中，为什么首元素的地址为 0)
int arr[5] = {10, 20, 30, 40, 50};
// 索引从0开始
arr[0] = 10 // 第1个元素
arr[1] = 20 // 第2个元素
arr[2] = 30 // 第3个元素
arr[3] = 40 // 第4个元素
arr[4] = 50 // 第5个元素
// arr[5] 是越界访问，危险！
为什么从0开始？
- 数学简洁性：地址 = 基址 + 索引 × 元素大小
- 如果从1开始：地址 = 基址 + (索引-1) × 元素大小（多了减法）
数组的内存布局
数组在内存中的存储方式
让我们看一个具体的例子：
int arr[4] = {100, 200, 300, 400};
在内存中的布局：
内存地址: 2000 2004 2008 2012
数组内容: [100] [200] [300] [400]
索引: 0 1 2 3
变量名: arr[0] arr[1] arr[2] arr[3]
关键点：
- 每个int占4字节
- 地址连续递增
- arr变量存储的是首元素的地址（2000）
为什么数组访问这么快？
直接地址计算：不需要遍历，直接计算出地址
硬件支持：CPU可以快速进行地址计算
缓存友好：连续存储利于CPU缓存
对比其他数据结构：
// 数组访问：O(1)
int value = arr[100]; // 直接计算地址访问
// 链表访问：O(n)
ListNode* current = head;
for(int i = 0; i < 100; i++) {
current = current->next; // 需要逐个遍历
}
int value = current->data;
数组的基本操作
数组的声明和初始化
C++中的数组声明：
// 方式1：声明后赋值
int arr[5];
arr[0] = 1;
arr[1] = 2;
// ...
// 方式2：声明时初始化
int arr[5] = {1, 2, 3, 4, 5};
// 方式3：部分初始化（其余为0）
int arr[5] = {1, 2}; // {1, 2, 0, 0, 0}
// 方式4：自动推导大小
int arr[] = {1, 2, 3, 4, 5}; // 编译器推导为5个元素
// 方式5：全部初始化为0
int arr[5] = {0}; // {0, 0, 0, 0, 0}
元素访问（读取和修改）
读取元素：
int arr[5] = {10, 20, 30, 40, 50};
int first = arr[0]; // 读取第一个元素：10
int third = arr[2]; // 读取第三个元素：30
int last = arr[4]; // 读取最后一个元素：50
修改元素：
arr[1] = 100; // 将第二个元素改为100
arr[3] += 5; // 第四个元素增加5
++arr[4]; // 最后一个元素自增1
// 现在数组变为：{10, 100, 30, 45, 51}
安全访问的建议：
int arr[5] = {1, 2, 3, 4, 5};
int size = 5;
// 好的做法：检查边界
int index = 7;
if (index >= 0 && index < size) {
int value = arr[index];
} else {
cout << "索引越界!" << endl;
}
// C++11的at()方法（对于std::array）
#include <array>
std::array<int, 5> arr = {1, 2, 3, 4, 5};
try {
int value = arr.at(7); // 会抛出异常
} catch (const std::out_of_range& e) {
cout << "索引越界: " << e.what() << endl;
}
遍历数组的几种方式（注意学习一下方式 2）
1. 传统for循环：
int arr[5] = {1, 2, 3, 4, 5};
int size = 5;
for (int i = 0; i < size; i++) {
cout << "arr[" << i << "] = " << arr[i] << endl;
}
2. 范围for循环（C++11）：
int arr[] = {1, 2, 3, 4, 5};
for (int element : arr) {
cout << element << " ";
}
cout << endl;
// 如果需要修改元素，使用引用
for (int& element : arr) {
element *= 2; // 每个元素乘以2
}
3. 指针遍历：
int arr[5] = {1, 2, 3, 4, 5};
for (int* ptr = arr; ptr < arr + 5; ptr++) {
cout << *ptr << " ";
}
cout << endl;
4. 使用迭代器（std::array）：
#include <array>
std::array<int, 5> arr = {1, 2, 3, 4, 5};
for (auto it = arr.begin(); it != arr.end(); ++it) {
cout << *it << " ";
}
cout << endl;
下面给大家说一下数组边界问题
数组边界检查的重要性
越界访问的危险：
int arr[5] = {1, 2, 3, 4, 5};
// 危险：读取越界
int dangerous = arr[10]; // 读取未知内存，可能是垃圾值
// 更危险：写入越界
arr[10] = 999; // 可能覆盖其他变量，导致程序崩溃
常见的越界错误：
int arr[10];
// 循环条件错误
for (int i = 0; i <= 10; i++) { // 应该是 i < 10
arr[i] = i; // 当i=10时越界
}
// 负索引
int index = -1;
arr[index] = 5; // 越界访问
// 错误3：使用未初始化的索引
int index;
arr[index] = 5; // index是垃圾值，可能越界
防范措施：
// 使用常量定义大小
const int SIZE = 10;
int arr[SIZE];
for (int i = 0; i < SIZE; i++) { // 使用SIZE而不是硬编码
arr[i] = i;
}
// 使用sizeof计算大小（仅适用于静态数组）
int arr[10];
int size = sizeof(arr) / sizeof(arr[0]);
// 使用std::array（推荐）
#include <array>
std::array<int, 10> arr;
for (size_t i = 0; i < arr.size(); i++) {
arr[i] = i;
}
// 边界检查函数
bool isValidIndex(int index, int size) {
return index >= 0 && index < size;
}
int safeAccess(int arr[], int size, int index) {
if (isValidIndex(index, size)) {
return arr[index];
} else {
throw std::out_of_range("Index out of bounds");
}
}
好啦，上面的内容学的差不多了，下面咱们来看一下不同的数组
一维数组详解
一维数组的创建
一维数组是最简单的数组形式，就像一条直线上排列的盒子。
静态创建（编译时确定大小）：
// C++
int staticArray[10]; // 创建10个整数的数组
double prices[5] = {1.2, 3.4, 5.6, 7.8, 9.0};
char name[20] = "Hello"; // 字符数组
// 在栈上创建，生命周期有限
void function() {
int localArray[100]; // 函数结束时自动销毁
}
动态创建（运行时确定大小）：
// C++ 动态数组
int size = 100;
int* dynamicArray = new int[size]; // 在堆上创建
// 使用完后必须释放
delete[] dynamicArray;
// 更好的方式：使用智能指针
#include <memory>
auto smartArray = std::make_unique<int[]>(size);
// 自动释放，不需要手动delete
// 或者使用std::vector（推荐）
#include <vector>
std::vector<int> vec(size); // 动态数组，自动管理内存
一维数组常见操作示例
查找操作：
// 线性查找
int linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return i; // 返回找到的索引
}
}
return -1; // 未找到
}
// 使用示例
int numbers[] = {3, 7, 2, 9, 1, 5};
int size = 6;
int index = linearSearch(numbers, size, 9);
if (index != -1) {
cout << "找到了，在索引 " << index << endl;
}
插入操作：
// 在指定位置插入元素（需要移动后面的元素）
bool insertElement(int arr[], int& size, int capacity, int index, int value) {
// 检查边界
if (size >= capacity || index < 0 || index > size) {
return false;
}
// 从后往前移动元素
for (int i = size; i > index; i--) {
arr[i] = arr[i - 1];
}
// 插入新元素
arr[index] = value;
size++;
return true;
}
// 使用示例
int arr[10] = {1, 2, 4, 5}; // capacity=10, size=4
int size = 4;
insertElement(arr, size, 10, 2, 3); // 在索引2插入值3
// 结果：{1, 2, 3, 4, 5}, size=5
删除操作：
// 删除指定位置的元素
bool deleteElement(int arr[], int& size, int index) {
if (index < 0 || index >= size) {
return false;
}
// 从删除位置开始，每个元素向前移动
for (int i = index; i < size - 1; i++) {
arr[i] = arr[i + 1];
}
size--;
return true;
}
排序操作（冒泡排序）：
void bubbleSort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
bool swapped = false;
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换元素
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// 如果没有交换发生，数组已经排序好了
if (!swapped) break;
}
}
数组反转：
void reverseArray(int arr[], int size) {
int start = 0;
int end = size - 1;
while (start < end) {
// 交换首尾元素
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
// 使用示例
int arr[] = {1, 2, 3, 4, 5};
reverseArray(arr, 5);
// 结果：{5, 4, 3, 2, 1}
一维数组的应用场景
存储内容（下面以学生成绩举例）
const int STUDENT_COUNT = 30;
double scores[STUDENT_COUNT];
// 计算平均分
double calculateAverage(double scores[], int count) {
double sum = 0;
for (int i = 0; i < count; i++) {
sum += scores[i];
}
return sum / count;
}
// 找最高分
double findMaxScore(double scores[], int count) {
double max = scores[0];
for (int i = 1; i < count; i++) {
if (scores[i] > max) {
max = scores[i];
}
}
return max;
}
统计字符频率（刷题时常用，大家可以学习一下这个思想）
void countCharacters(const string& text) {
int frequency[256] = {0}; // ASCII字符频率数组
// 统计每个字符的出现次数
for (char c : text) {
frequency[static_cast<unsigned char>(c)]++;
}
// 输出结果
for (int i = 0; i < 256; i++) {
if (frequency[i] > 0) {
cout << "字符 '" << static_cast<char>(i)
<< "' 出现了 " << frequency[i] << " 次" << endl;
}
}
}
简单的缓存实现（项目中可以借鉴）
class SimpleCache {
private:
static const int CACHE_SIZE = 100;
int keys[CACHE_SIZE];
int values[CACHE_SIZE];
bool used[CACHE_SIZE];
public:
SimpleCache() {
for (int i = 0; i < CACHE_SIZE; i++) {
used[i] = false;
}
}
void put(int key, int value) {
// 简单的线性探测
for (int i = 0; i < CACHE_SIZE; i++) {
if (!used[i] || keys[i] == key) {
keys[i] = key;
values[i] = value;
used[i] = true;
return;
}
}
}
bool get(int key, int& value) {
for (int i = 0; i < CACHE_SIZE; i++) {
if (used[i] && keys[i] == key) {
value = values[i];
return true;
}
}
return false;
}
};
多维数组
二维数组的概念
二维数组可以理解为"数组的数组"，就像一个表格或矩阵：
二维数组示例（3x4矩阵）：
列0 列1 列2 列3
行0 1 2 3 4
行1 5 6 7 8
行2 9 10 11 12
声明和初始化：
// 方式1：声明并初始化
int matrix[3][4] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
};
// 方式2：部分初始化
int matrix[3][4] = {
{1, 2}, // 其余元素自动为0
{5}, // {5, 0, 0, 0}
{} // {0, 0, 0, 0}
};
访问元素：
int matrix[3][4] = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12}};
// 读取元素
int value = matrix[1][2]; // 第2行第3列的元素：7
// 修改元素
matrix[0][0] = 100; // 修改第1行第1列
// 错误的访问方式
// int wrong = matrix[3][4]; // 越界访问！
多维数组的内存布局
行优先存储（Row-major order）：
大多数编程语言（包括C++、Java）使用行优先存储：
int matrix[3][4] = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12}};
内存中的实际布局：
地址: 1000 1004 1008 1012 1016 1020 1024 1028 1032 1036 1040 1044
元素: 1 2 3 4 5 6 7 8 9 10 11 12
位置: [0][0][0][1][0][2][0][3][1][0][1][1][1][2][1][3][2][0][2][1][2][2][2][3]
地址计算公式：
对于数组 arr[M][N]，元素 arr[i][j] 的地址：
地址 = 基址 + (i * N + j) * 元素大小
示例：
int matrix[3][4]; // 假设基址是1000，int占4字节
// matrix[1][2] 的地址：
// 地址 = 1000 + (1 * 4 + 2) * 4 = 1000 + 6 * 4 = 1024
列优先存储（Column-major order）：
某些语言如Fortran、MATLAB使用列优先：
同样的矩阵，列优先存储在内存中为：
1 5 9 2 6 10 3 7 11 4 8 12
多维数组的遍历技巧
标准遍历：
int matrix[3][4] = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12}};
// 按行遍历
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 4; j++) {
cout << matrix[i][j] << " ";
}
cout << endl;
}
使用范围for循环（C++11）：
int matrix[3][4] = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12}};
for (auto& row : matrix) {
for (auto& element : row) {
cout << element << " ";
}
cout << endl;
}
螺旋遍历（比较常考的算法题）
void spiralTraversal(int matrix[][4], int rows, int cols) {
int top = 0, bottom = rows - 1;
int left = 0, right = cols - 1;
while (top <= bottom && left <= right) {
// 从左到右
for (int j = left; j <= right; j++) {
cout << matrix[top][j] << " ";
}
top++;
// 从上到下
for (int i = top; i <= bottom; i++) {
cout << matrix[i][right] << " ";
}
right--;
// 从右到左（如果还有行）
if (top <= bottom) {
for (int j = right; j >= left; j--) {
cout << matrix[bottom][j] << " ";
}
bottom--;
}
// 从下到上（如果还有列）
if (left <= right) {
for (int i = bottom; i >= top; i--) {
cout << matrix[i][left] << " ";
}
left++;
}
}
}
// 对于4x4矩阵，输出：1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
数组的时间复杂度分析
时间复杂度是衡量算法效率的重要指标。理解数组各种操作的时间复杂度对于选择合适的数据结构至关重要。
访问操作：O(1)
数组的最大优势就是常数时间的随机访问：
int arr[1000];
int value = arr[500]; // O(1) - 直接通过地址计算访问
为什么是O(1)？
- 地址计算公式：
地址 = 基址 + 索引 × 元素大小 - 这个计算只需要一次算术运算，与数组大小无关
- CPU可以直接跳转到计算出的内存地址
对比其他数据结构：
// 数组访问：O(1)
int value = arr[100];
// 链表访问：O(n)
ListNode* current = head;
for (int i = 0; i < 100; i++) {
current = current->next;
}
int value = current->data;
// 哈希表访问：O(1) 平均，O(n) 最坏
int value = hashMap[key];
搜索操作：O(n)
在未排序的数组中搜索元素需要遍历：
// 线性搜索：O(n)
int linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; i++) { // 最多需要检查n个元素
if (arr[i] == target) {
return i;
}
}
return -1;
}
// 最佳情况：O(1) - 第一个元素就是目标
// 平均情况：O(n/2) ≈ O(n) - 平均需要检查一半元素
// 最坏情况：O(n) - 目标在最后或不存在
对于排序数组，可以使用二分搜索：O(log n)
// 二分搜索：O(log n)
int binarySearch(int arr[], int size, int target) {
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 避免溢出
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
// 每次循环将搜索范围减半
// 循环次数：log₂(n)
插入操作：O(n)
在数组中插入元素通常需要移动其他元素：
// 在指定位置插入：O(n)
bool insert(int arr[], int& size, int capacity, int index, int value) {
if (size >= capacity || index < 0 || index > size) {
return false;
}
// 从后往前移动元素 - 最多移动n个元素
for (int i = size; i > index; i--) { // O(n)
arr[i] = arr[i - 1];
}
arr[index] = value;
size++;
return true;
}
不同位置插入的时间复杂度：
- 头部插入：O(n) - 需要移动所有元素
- 中间插入：O(n) - 需要移动一半元素（平均）
- 尾部插入：O(1) - 不需要移动元
动态数组的插入（如std::vector）：
vector<int> vec;
vec.push_back(42); // O(1) 平均，O(n) 最坏（扩容时）
vec.insert(vec.begin(), 42); // O(n) - 在开头插入
删除操作：O(n)
删除元素也需要移动后续元素：
// 删除指定位置的元素：O(n)
bool deleteElement(int arr[], int& size, int index) {
if (index < 0 || index >= size) {
return false;
}
// 从删除位置开始，元素前移 - 最多移动n个元素
for (int i = index; i < size - 1; i++) { // O(n)
arr[i] = arr[i + 1];
}
size--;
return true;
}
不同位置删除的时间复杂度：
- 头部删除：O(n) - 需要移动所有剩余元素
- 中间删除：O(n) - 需要移动一半元素（平均）
- 尾部删除：O(1) - 不需要移动元素
