数据结构

1 说说一个算法有哪些时间复杂度？归并算法时间复杂度是多少？⭐⭐⭐⭐⭐

一个算法的时间复杂度通常包括以下常见类型及对应典型算法示例‌：

‌O(1)‌

常数时间复杂度

示例：数组随机访问、绝对值计算（如 abs(x)）

‌O(n)‌

线性时间复杂度

示例：线性查找、计数排序、基数排序

‌O(n²)‌

平方时间复杂度

示例：冒泡排序、插入排序、选择排序

‌O(logn)‌

对数时间复杂度

示例：二分查找、最大公约数计算（如 __gcd(a,b)）

‌O(n logn)‌

线性对数时间复杂度

示例：快速排序（平均情况）、归并排序、堆排序

‌O(2ⁿ)‌

指数时间复杂度

示例：穷举法解决子集问题

‌归并排序的时间复杂度‌为 ‌O(n logn)‌，具体分析如下‌：

• 分治策略‌：归并排序将数组递归拆分为两半，拆分次数为 log₂n 层。
• ‌合并操作‌：每层合并需要 O(n) 时间遍历所有元素。
• ‌总复杂度‌：O(n) × O(logn) = O(n logn)。

其时间复杂度在所有情况下（最好/平均/最坏）均保持稳定，是高效且稳定的排序算法。

2 说说数组时间复杂度，什么场景下使用？⭐⭐⭐

一、数组的时间复杂度分析

数组作为线性数据结构，其时间复杂度主要取决于操作类型：

‌随机访问‌：通过下标直接访问元素，时间复杂度为 ‌O(1)‌（如 array[i]）‌。

‌插入/删除‌：

在数组末尾操作，时间复杂度为 ‌O(1)‌（如动态扩容前的追加操作）‌。

在中间或开头操作，需移动后续元素，时间复杂度为 ‌O(n)‌（如插入到第k个位置）‌。

‌遍历操作‌：遍历所有元素的时间复杂度为 ‌O(n)‌‌。

二、数组的适用场景

数组因其内存连续、访问高效的特点，适用于以下场景：

‌存储固定大小的数据集合‌

如存储学生成绩、用户信息等已知数量的同类型数据‌。

示例：Java中静态初始化 int[] scores = {90, 85, 78};‌。

‌需要高频随机访问的场景‌

如算法中的二分查找、快速排序等依赖下标快速定位的场景‌。

示例：Arrays.binarySearch() 实现依赖于数组的随机访问特性‌。

‌多维数据表示‌

如矩阵运算、图像像素存储等需要多维结构的场景‌。

示例：二维数组表示棋盘 int[][] chessBoard = new int;‌。

‌缓存优化与性能敏感场景‌

内存连续特性可提高CPU缓存命中率，适用于底层开发（如网络框架）‌。

‌批量数据操作‌

如遍历统计、批量修改等需要顺序访问的场景（如计算平均分）‌。

三、总结

数组在‌随机访问性能强、数据规模固定、内存连续‌的场景下表现优异，但插入/删除效率低且扩容成本高‌。实际开发中需根据需求权衡其优缺点，例如在需要动态扩容时，可结合链表或 ArrayList 使用。

3 说说vector的实现原理⭐⭐⭐⭐

vector 是 C++ 标准模板库（STL）中的一个容器，它实现了动态数组的功能。以下是 vector 的实现原理的详细介绍：

数据存储

vector 内部使用一块连续的内存空间来存储元素。这就像在内存中开辟了一段连续的 “线性空间”，元素按照顺序依次存放，这种连续存储的方式使得 vector 可以像数组一样通过下标快速访问元素，时间复杂度为 O (1)。

动态增长机制

vector 能够根据需要动态地调整自身的大小。当向 vector 中插入元素时，如果当前的内存空间已满，vector 会自动分配一块更大的内存空间，通常是当前容量的两倍，然后将原来的元素复制到新的内存空间中，最后释放原来的内存空间。

以一个初始容量为 5 的 vector 为例，当插入第 6 个元素时，vector 会分配一块容量为 10 的新内存空间，将前 5 个元素复制到新空间，再插入第 6 个元素，然后释放原来容量为 5 的内存空间。

迭代器

vector 提供了迭代器来访问和遍历容器中的元素。迭代器在 vector 中的工作原理类似于指针，它可以指向 vector 中的某个元素，通过迭代器的移动操作，可以顺序访问 vector 中的每个元素。

可以使用 begin () 函数获取指向 vector 第一个元素的迭代器，使用 end () 函数获取指向 vector 最后一个元素的下一个位置的迭代器。

元素插入和删除

插入操作：当在 vector 的任意位置插入元素时，需要将插入位置之后的元素依次向后移动，为新元素腾出空间，然后将新元素插入到指定位置。如果插入位置是 vector 的末尾，直接将元素插入到末尾即可，时间复杂度通常为 O (1)；但如果是在 vector 的开头或中间插入元素，时间复杂度为 O (n)，n 为 vector 中元素的个数。

删除操作：删除 vector 中的元素时，需要将删除位置之后的元素依次向前移动，填补被删除元素的位置，以保持内存的连续性。同样，如果删除的是 vector 的末尾元素，时间复杂度为 O (1)；如果删除的是开头或中间的元素，时间复杂度为 O (n)。

内存管理

vector 负责管理自己的内存空间，在创建 vector 对象时，会根据初始容量分配一定大小的内存空间。当 vector 对象被销毁时，会自动释放其所占用的内存空间，防止内存泄漏。

在 vector 的大小发生变化时，它会合理地申请和释放内存，以确保在满足存储需求的同时，尽可能地提高内存的使用效率。

4 总结一下数组与链表的区别⭐⭐⭐⭐

存储结构：数组是连续存储，链表是节点式的非连续存储。

访问方式：数组可通过下标随机访问，时间复杂度为 O (1)；链表需顺序访问，时间复杂度为 O (n)。

插入删除操作：数组在中间或头部插入删除需移动大量元素，时间复杂度为 O (n)；链表只需修改指针，时间复杂度一般为 O (1)。

内存分配：数组静态分配内存，大小固定；链表动态分配内存，大小可灵活变化。

5 栈和队列的区别⭐⭐⭐⭐

栈和队列的区别主要体现在：

数据进出原则：栈遵循后进先出（LIFO）原则，如同弹夹，最后压入的子弹最先弹出；队列遵循先进先出（FIFO）原则，类似排队，先到的先处理。

操作方式：栈的插入和删除操作都在栈顶进行；队列的插入在队尾，删除在队头。

应用场景：栈常用于函数调用、表达式求值等；队列常用于任务调度、缓存管理等。

6 说说二叉堆⭐⭐⭐

二叉堆是一种基于完全二叉树的数据结构，常用于实现优先队列。以下是关于二叉堆的详细说明：

一、核心概念

1. 定义完全二叉树：除最后一层外，其他层节点填满，且最后一层节点从左到右排列。堆性质：最大堆：每个节点的值 ≥ 其子节点的值。最小堆：每个节点的值 ≤ 其子节点的值。
2. 存储方式使用数组存储，无需额外指针。节点 i 的子节点为 2i+1（左）和 2i+2（右），父节点为 (i-1)/2。

二、关键操作

1. 插入（以最小堆为例）将元素添加到数组末尾。向上调整（Shift Up）：若新元素小于父节点，与父节点交换，重复直到满足堆性质。
2. 删除（以最小堆为例）删除根节点（最小值）。用最后一个元素填补根节点位置。向下调整（Shift Down）：若当前节点大于子节点，与较小子节点交换，重复直到满足堆性质。
3. 堆化（Heapify）将普通数组转换为堆结构。从最后一个非叶子节点开始，逐个节点向下调整。

三、应用场景

1. 优先队列：快速获取最大 / 最小值。
2. 堆排序：通过堆结构实现高效排序。
3. 图算法：如 Dijkstra 算法（求最短路径）。
4. 找第 K 大 / 小元素：用堆优化时间复杂度。

7 说说哈希表⭐⭐⭐

哈希表（Hash Table）是一种通过哈希函数实现快速查找、插入和删除的数据结构，其核心思想是将键映射到存储位置。以下是关于哈希表的详细说明：

一、核心概念

1. 定义哈希表由 键值对（Key-Value