数据结构 常见面试题

数据结构

了解哪些数据结构？

• 数组：数组的内存空间是连续的，随机访问的时间复杂度是O1，适用于需要按索引访问元素的 场景，但是插入和删除元素较慢，时间复杂度是On
• 链表：链表是由节点组成，节点之间是分散存储的，内存不连续，每个节点存储数据和指向下 一个节点的指针。适用于频繁插入和删除元素的场景，随机访问元素较慢。
• 栈：栈是一种后进先出的数据结构，只允许在栈顶进行插入和删除操作。
• 队列：队列是一种先进先出（FIFO）的数据结构，允许在队尾插入元素，在队首删除元素。
• 树：树是一种非线性数据结构，由节点和边组成，每个节点可以有多个子节点。树适用于表示 层次关系的场景，例如文件系统、组织结构等。

数组和链表区别是什么？

• 访问效率：数组可以通过索引直接访问任何位置的元素，访问效率高，时间复杂度为O(1)，而链表需要从头节点开始遍历到目标位置，访问效率较低，时间复杂度为O(n)
• 缓存命中率：由于数组元素在内存中连续存储，可以提高CPU缓存的命中率，而链表节点不连续存储，可能导致CPU缓存的命中率较低，频繁的缓存失效会影响性能。
• 应用场景：数组适合静态大小、频繁访问元素的场景，而链表适合动态大小、频繁插入、删除 操作的场景.

为什么数组查询的复杂度为O(1)？

数组必须要内存中一块连续的空间，并且数组中必须存放相同的数据类型。

利用这个特性，我们只要知道了数组下标，也就是数据在数组中的位置，比如下标 2，就可以计算 得到这个数据在内存中的位置 1008，从而对这个位置的数据 241 进行快速读写访问，时间复杂度 为 O(1)。

说一下队列和栈的区别

主要区别在于元素的插入和删除方式以及元素的访问顺序。

• 插入和删除方式：
  • 队列：队列采用先进先出（FIFO）的方式，即新元素插入队尾，删除操作发生在队首。
  • 栈：栈采用后进先出（LIFO）的方式，即新元素插入栈顶，删除操作也发生在栈顶。
• 元素的访问顺序：
  • 队列：队列的元素按照插入的顺序进行访问，先插入的元素先被访问到。
  • 栈：栈的元素按照插入的顺序进行访问，但是最后插入的元素先被访问到。

队列适用于需要按照插入顺序进行处理的场景，例如任务调度；而栈适用于需要维护最近操作状态的场景，例如函数调用。

如何使用两个栈实现队列？

详细请查看：用栈实现队列以及队列实现栈

平衡二叉树结构是怎么样的？

使用二叉树搜索树的目的之一是缩短插入、删除、修改和查找（插入、删除、修改都包括查找操 作）节点的时间。

关于查找效率，如果一棵树的高度为h，在最坏的情况，查找一个关键字需要对比 h 次，查找时间 复杂度不超过 O(h)。一棵理想的二叉搜索树所有操作的时间可以缩短到 O(logn)（n 是节点总 数)。

然而 O(h) 的时间复杂度仅为理想情况。在最坏情况下，搜索树有可能退化为链表。想象一棵每个 结点只有右孩子的二叉搜索树，那么它的性质就和链表一样，所有操作（增删改查）的时间是 O(n)。

可以发现操作的复杂度与树的高度 h 有关。由此引出了平衡树，通过一定操作维持树的高度（平 衡性）来降低操作的复杂度。

所谓的平衡树是指一种改进的二叉查找树，顾名思义平衡树就是将二叉查找树平衡均匀地分布， 这样的好处就是可以减少二叉查找树的深度。

一般情况下二叉查找树的查询复杂度取决于目标节点到树根的距离（即深度），当节点的深度普 遍较大时，查询的平均复杂度就会上升，因此为了实现更高效的查询就有了平衡树。

平衡二叉树平衡的特性：

• 左右两个子树的高度差（平衡因子）的绝对值不超过1
• 左右两个子树都是一棵平衡二叉树

红黑树了解吗？

红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它在插入和删除操作后能够通过旋转和重 新着色来保持树的平衡。

红黑树的特点如下：

• 每个节点要么是黑色，要么是红色。
• 根节点是黑色。
• 每个叶子节点（NIL）是黑色。
• 每个红色结点的两个子结点一定都是黑色。
• 任意一结点(包含本身)到其叶子结点的路径都包含数量相同的黑结点。

红黑树通过这些特性来保持树的平衡，确保最长路径不超过最短路径的两倍，从而保证了在最坏情况下的搜索、插入和删除操作的时间复杂度都为O(logN)。

应用场景：

• epoll 用了红黑树来保存监听的 socket；
• TreeMap、TreeSet，HashMap、HashSet底层都用了红黑树结构。

跳表了解吗？

特点：

1. 跳表中的数据是有序的。
2. 跳表中的每个节点都包含一个指向下一层和右侧节点的指针。

时间复杂度：

• 搜索操作的时间复杂度：O(log n)，其中n是跳表中元素的数量。这是因为跳表中使用多级索 引，可以通过跳跃的方式快速定位到目标元素所在的位置，从而将搜索的时间复杂度降低到对 数级别。
• 插入和删除操作的时间复杂度：O(log n)，其中n是跳表中元素的数量。与搜索操作类似，插入和删除操作也可以通过跳跃的方式快速定位到需要插入或删除的位置，并进行相应的操作。因此，插入和删除的时间复杂度也是对数级别的。

跳表通过多层索引的方式来加速搜索操作。最底层是一个普通的有序链表，而上面的每一层都是 前一层的子集，每个节点在上一层都有一个指针指向它在下一层的对应节点。这样，在搜索时可 以通过跳过一些节点，直接进入目标区域，从而减少搜索的时间复杂度。

跳表的平均搜索、插入和删除操作的时间复杂度都为O(logN)，与红黑树相比，跳表的实现更加简 单，但空间复杂度稍高。跳表常用于需要高效搜索和插入操作的场景，如数据库、缓存等。

应用场景：redis 用了跳表来实现 zset

B+树的特点是什么？

• B+树是一种自平衡的多路查找树，所有叶节点都位于同一层，保证了树的平衡，使得搜索、插 入和删除操作的时间复杂度为对数级别的。
• 非叶节点仅包含索引信息，不存储具体的数据记录，它们只用来引导搜索到正确的叶节点。非 叶节点的子树指针与关键字数量相同，每个子树指针指向一个子树，子树中的所有键值都在某 个区间内。
• 所有数据记录都存储在叶节点中，且叶节点中的数据是按关键字排序的。叶节点包含实际的数 据和关键字，它们是数据存储和检索的实体单元。叶节点之间通过指针相互链接，形成一个链 表，便于范围查询和顺序遍历。

B+树和B树有什么不一样，B+树的叶子节点和非叶子节点有什么不一样， 非叶子节点会不会存数据？

• 检索路径：B树在查找数据时，可能在非叶子节点找到目标数据，路径长度不固定。即查找时可 以在任意一个节点终止。B+树中所有数据都在叶子节点，查找数据时必须走到叶子节点，路径 长度固定（均等）。即查找总是要到叶子节点结束。
• 叶子节点结构：B树中叶子节点之间没有特别的链接，彼此独立。B+树中叶子节点通过指针连接，形成一个有序链表，便于范围查询和顺序访问。
• 非叶子节点内容：B树中非叶子节点存储数据和索引。B+树中非叶子节点只存储索引，不存储实际数据。因此，当数据量比较大时，相对于B树，B+树的层高更少，查找效率也就更高。
• 高效地范围查询：B+树叶子节点采用的是双链表连接，适合 MySQL 中常见的基于范围的顺 序查找，而 B 树在进行范围查询时需要进行中序遍历，性能较差。

堆是什么？

堆是一颗完全二叉树，这样实现的堆也被称为二叉堆。堆中节点的值都大于等于（或小于等于） 其子节点的值，堆中如果节点的值都大于等于其子节点的值，我们把它称为大顶堆，如果都小于 等于其子节点的值，我们将其称为小顶堆。

LRU是什么？

如何实现？ LRU 是一种缓存淘汰算法，当缓存空间已满时，优先淘汰最长时间未被访问的数据。 实现的方式是哈希表+双向链表结合。

详细请查看：LinkedHashSet & Map详解,LRU & LFU

了解布隆过滤器吗？

详细请查看：布隆过滤器

排序算法

排序算法可以分为：

• 内部排序：数据记录在内存中进行排序。
• 外部排序：因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等，本文只讲解内部排序算法。用一张图概括：

• 冒泡排序：通过相邻元素的比较和交换，每次将最大（或最小）的元素逐步“冒泡”到最后（或最前）。时间复杂度：最好情况下$O(n)$，最坏情况下$O(n^2)$，平均情况下$O(n^2)$。，空间复杂 度：$O(1)$。
• 插入排序：将待排序元素逐个插入到已排序序列的合适位置，形成有序序列。时间复杂度：最好情况下$O(n)$，最坏情况下$O(n^2)$，平均情况下$O(n^2)$，空间复杂度：$O(1)$。
• 选择排序（Selection Sort）：通过不断选择未排序部分的最小（或最大）元素，并将其放置在 已排序部分的末尾（或开头）。时间复杂度：最好情况下$O(n^2)$，最坏情况下$O(n^2)$，平均情 况下$O(n^2)$，空间复杂度：$O(1)$。
• 快速排序（Quick Sort）：通过选择一个基准元素，将数组划分为两个子数组，使得左子数组的元素都小于（或等于）基准元素，右子数组的元素都大于（或等于）基准元素，然后对子数组进行递归排序。时间复杂度：最好情况下$O(nlogn)$，最坏情况下$O(n^2)$，平均情况下$O(nlogn)$，空间复杂度：最好情况下$O(logn)$，最坏情况下$O(n)$。
• 归并排序（Merge Sort）：将数组不断分割为更小的子数组，然后将子数组进行合并，合并过 程中进行排序。时间复杂度：最好情况下$O(nlogn)$，最坏情况下$O(nlogn)$，平均情况下 $O(nlogn)$。空间复杂度：$O(n)$。
• 堆排序（Heap Sort）：通过将待排序元素构建成一个最大堆（或最小堆），然后将堆顶元素与 末尾元素交换，再重新调整堆，重复该过程直到排序完成。时间复杂度：最好情况下 $O(nlogn)$，最坏情况下$O(nlogn)$，平均情况下$O(nlogn)$。空间复杂度：$O(1)$。

讲一下快排原理

快排使用了分治策略的思想，所谓分治，顾名思义，就是分而治之，将一个复杂的问题，分成两 个或多个相似的子问题，在把子问题分成更小的子问题，直到更小的子问题可以简单求解，求解 子问题，则原问题的解则为子问题解的合并。

快排的过程简单的说只有三步：
首先从序列中选取一个数作为基准数 将比这个数大的数全部放到它的右边，把小于或者等于它的数全部放到它的左边 （一次快排 partition ）
然后分别对基准的左右两边重复以上的操作，直到数组完全排序

具体按以下步骤实现：

1. 创建两个指针分别指向数组的最左端以及最右端
2. 在数组中任意取出一个元素作为基准
3. 左指针开始向右移动，遇到比基准大的停止
4. 右指针开始向左移动，遇到比基准小的元素停止，交换左右指针所指向的元素
5. 重复3，4，直到左指针超过右指针，此时，比基准小的值就都会放在基准的左边，比基准大 的值会出现在基准的右边
6. 然后分别对基准的左右两边重复以上的操作，直到数组完全排序

注意这里的基准该如何选择？最简单的一种做法是每次都是选择最左边的元素作为基准，但这对 几乎已经有序的序列来说，并不是最好的选择，它将会导致算法的最坏表现。还有一种做法，就 是选择中间的数或通过 Math.random() 来随机选取一个数作为基准。

快速排序的简洁版流程如下：

1. 从数组中选择一个基准元素（通常是数组最左边的元素）。
2. 将数组分成两部分，小于基准元素的放在左边，大于基准元素的放在右边。
3. 递归地对左右两部分进行快速排序。

快速排序的时间复杂度为O(n log n)，其中n为数组的长度。最坏情况下时间复杂度为O(n^2)，发 生在每次选择的基准元素都是最大或最小值时。平均情况下时间复杂度为O(n log n)，效率较高。

堆排序算法原理，稳定吗？

整个堆排序的过程中，只需要个别的临时存储空间，所以堆排序是原地排序算法。

堆排序包括建堆和排序两个操作，建堆的时间复杂度是O(n)，排序过程时间复杂度是 O(nlogN)。所以，堆排序的整个时间复杂度是O(nlogN)。

因为在排序的过程中，存在将堆的最后一个节点跟堆顶互换的操作，所以有可能会改变值相同 数据的原始相对顺序，所以堆排序不是稳定的排序算法。例如，假设我们有两个相同的元素A和 B，且A在B前面。在构建和调整堆的过程中，B可能被移动到A的前面，从而破坏了它们原来的 相对顺序。

归并排序和快速排序的使用场景

归并排序是稳定排序算法，适合排序稳定的场景；

快速排序是不稳定排序算法，不适合排序稳定的场景，快速排序是目前基于比较的内部排序中 被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；

什么是排序稳定性？

排序算法的稳定性是指在排序过程中，当有多个具有相同关键字的元素时，这些元素在排序后的 序列中保持它们原有的相对顺序。

换句话说，如果两个元素有相同的键值，那么在排序前，如果第一个元素在第二个元素之前，排 序后第一个元素也应该在第二个元素之前。

具体来说，对于一个序列中的两个元素A和B，如果A和B的键值相同，且在排序前A在B之前，那么 在排序后A仍然应该在B之前，算法才能被称为是稳定的。

快排为什么时间复杂度最差是O（n^2）？

主要是因为在每次划分时选择的基准元素不合适导致的。当每次选择的基准元素都是当前子数组中的最大或最小元素时，就会导致每次划分只能减少一个元素，而不是均匀地分成两部分，从而造成时间复杂度达到$O(n^2)$。

这种情况通常发生在数组已经有序或基本有序的情况下。为了避免最坏情况发生，可以通过随机选择基准元素或者使用三数取中法等策略来提高快速排序的性能；或者可以先使用洗牌算法，将数据打乱。

如果要对一个很大的数据集，进行排序，而没办法一次性在内存排序，这时 候怎么办？

可以使用外部排序来解决，基本思路分为两个阶段。

1. 部分排序阶段。

根据内存大小，将待排序的文件拆成多个部分，使得每个部分都是足以存入内存中的。然后 选择合适的内排序算法，将多个文件部分排序，并输出到容量可以更大的外存临时文件中，每个 临时文件都是有序排列的，我们将其称之为一个“顺段”。

在第一个阶段部分排序中，由于内存可以装下每个顺段的所有元素，可以使用快速排序，时间复 杂度是O(nlogn)。

2. 归并阶段

对前面的多个“顺段”进行合并，思想和归并排序其实是一样的。以 2 路归并为例，每次都将两 个连续的顺段合并成一个更大的顺段。

因为内存限制，每次可能只能读入两个顺段的部分内容，所以需要一部分一部分读入，在内 存里将可以确定顺序的部分排列，并输出到外存里的文件中，不断重复这个过程，直至两个顺段 被完整遍历。这样经过多层的归并之后，最终会得到一个完整的顺序文件。

归并阶段有个非常大的时间消耗就是 IO，也就是输入输出。最好就是让归并的层数越低越好，为了降低降低归并层数，可以使用败者树。

败者树中的非终端结点中存储的是胜利（左右孩子相比较，谁最小即为胜者）的一方；而败者树中的非终端结点存储的是失败的一方。而在比较过程中，都是拿胜者去比较。有了败者树的加持，多路归并排序就可以比较高效地解决外部排序的问题了。

大致思路就是：

1. 先用内排序算法（比如快速排序），尽可能多的加载源文件，将其变成 n 个有序顺段。
2. 在内存有限的前提下每 k 个文件为一组，每次流式地从各个文件中读取一个单词，借助败者树 选出字典序最低的一个，输出到文件中，这样就可以将 k 个顺段合并到一个顺段中了；反复执 行这样的操作，直至所有顺段被归并到同一个顺段。