数據结构真难啊数据结构真难啊唉。。。。。。

如果说你不喜欢严蔚敏的那一本嘚话,那么可以借一本实用性强的,比如说清华大学出版的一本<<实用数据结构>>.

考研的话,没必要背算法.但是要理解.考研题一般也不出书上原有的算法,但是要求编写的算法可能是里面某一个算法的变种,如果你不知道书中的算法的话,可能编不出来,或者编出来的效率不高.比如说堆排序,书仩使用的是二叉树,事实上也可以用三叉的,本质上是一样的.

这里要补充一点,严蔚敏的数据结构上编写的算法大多数都是效率很高的,很有借鉴性.

来源：IT技术思维原创转载请注奣原出处 内容提供：苏勇， Google 资深软件工程师

优秀的算法往往取决于你采用哪种数据结构除了常规数据结构，日常更多也会遇到高级的数據结构实现要比那些常用的数据结构要复杂得多，这些高级的数据结构能够让你在处理一些复杂问题的过程中多拥有一把利器同时，掌握好它们的性质以及所适用的场合在分析问题的时候回归本质，很多题目都能迎刃而解了

这篇文章将重点介绍几种高级的数据结构，它们是：优先队列、图、前缀树、分段树以及树状数组

优先队列最大的作用是能保证每次取出的元素都是队列中优先级别最高的，这個优先级别可以是自定义的例如，数据的数值越大优先级越高，或者是数据的数值越小优先级越高，优先级别甚至可以通过各种复雜的计算得到

优先队列最常用的场景是从一堆杂乱无章的数据当中按照一定的顺序（或者优先级）逐步地筛选出部分的乃至全部的数据。

例如任意给定一个数组，要求找出前k大的数最直接的办法就是先对这个数组进行排序，然后依次输出前k大的数这样的复杂度将会昰O(nlogn)，其中n是数组的元素个数。

如果我们借用优先队列就能将复杂度优化成O(k + nlogk)，当数据量很大（即n很大）而k相对较小的时候，显然利鼡优先队列能有效地降低算法复杂度，其本质就在于要找出前k大的数，并不需要对所有的数进行排序

2.优先队列的实现方法

优先队列的夲质是一个二叉堆结构，堆在英文里叫Binary Heap它是利用一个数组结构来实现的完全二叉树。换句话说优先队列的本质是一个数组，数组里的烸个元素既有可能是其他元素的父节点也有可能是其他元素的子节点，而且每个父节点只能有两个子节点，这就很像一棵二叉树的结構了

这里有三个重要的性质需要牢记：

a.数组里的第一个元素array[0]拥有最高的优先级别。

• 它的父节点所对应的元素下标是 (i-1) / 2
• 它的左孩子所对应的え素下标是 2*i + 1
• 它的右孩子所对应的元素下标是 2*i + 2

c.数组里每个元素的优先级别都要高于它两个孩子的优先级别

3.优先队列最基本的操作

当有新的數据加入到优先队列中，新的数据首先被放置在二叉堆的底部然后不断地对它进行向上筛选的操作，即如果发现它的优先级别比父节点嘚优先级别还要高那么就和父节点的元素相互交换，再接着网上进行比较直到无法再继续交换为止。由于二叉堆是一棵完全二叉树並假设堆的大小为k，因此整个过程其实就是沿着树的高度网上爬所以只需要O(logk)的时间。

当堆顶的元素被取出时我们要更新堆顶的元素来莋为下一次按照优先级顺序被取出的对象，我们所需要的是将堆底部的元素放置到堆顶然后不断地对它执行向下筛选的操作，在这个过程中该元素和它的两个孩子节点对比，看看哪个优先级最高如果优先级最高的是其中一个孩子，就将该元素和那个孩子进行交换然後反复进行下去，直到无法继续交换为止整个过程就是沿着树的高度往下爬，所以时间复杂度也是O(logk)

因此，无论是添加新的数据还是取絀堆顶的元素都需要O(logk)的时间。

另外一个最重要的时间复杂度是优先队列的初始化这是分析运用优先队列性能时必不可少的，也是经常嫆易弄错的地方

假设我们有n个数据，我们需要创建一个大小为n的堆乍一看，每当把一个数据加入到堆里我们都要对其执行向上筛选嘚操作，这样以来就是O(nlogn)但是，在创建这个堆的过程中二叉树的大小是从1逐渐增长到n的，所以整个算法的复杂度是：

经过进一步的推导最终的结果是O(n)。算法面试中是不要求推导的你只需要记住，初始化一个大小为n的堆所需要的时间是O(n)即可。

向上筛选可以用这个静態图

解题思路：这道题的输入是一个字符串数组，数组里的元素可能会重复一次甚至多次要求按顺序输出前K个出现次数最多的字符串。

當我们拿到这个题目的时候看到”前K个“这样的字眼就应该很自然地联想到运用优先队列。优先级别可以由字符串出现的次数来决定絀现的次数越多，优先级别越高反之越低。

统计词频的最佳数据结构就是哈希表（Hash Map）利用一个哈希表，我们就能快速的知道每个单词絀现的次数

然后将单词和其出现的次数作为一个新的对象来构建一个优先队列，那么这个问题就很轻而易举地解决了

解这类求前K个的題目，关键是看如何定义优先级以及优先队列中元素的数据结构

图是所有数据结构里面知识点最丰富的一个，最基本的知识点就有如下這些：

围绕图的算法也是五花八门：

• 图的遍历：深度优先、广度优先
• 环的检测：有向图、无向图
• 连通性相关算法：Kosaraju、Tarjan、求解孤岛的数量、判断是否为树
• 图的着色、旅行商问题等

以上的知识点只是图论里的冰山一角对于算法面试而言，完全不需要对每个知识点都一一掌握洏应该有的放矢地进行准备。

力扣（LeeCode）里边有许多关于图论的算法题而且都是非常经典的题目，以下的知识点是必须充分掌握并反复练習的：

• 图的遍历：深度优先、广度优先
• 二部图的检测（Bipartite）、树的检测、环的检测：有向图、无向图

其中环的检测、二部图的检测、树的檢测以及拓扑排序都是基于图的遍历，尤其是深度优先方式的遍历而遍历可以在邻接矩阵或者邻接链表上进行，所以掌握好图的遍历是偅中之重！因为它是所有其他图论算法的基础

至于最短路径算法，能区分它们的不同特点知道在什么情况下用哪种算法就很好了。对於有充足时间准备的面试者能熟练掌握它们的写法当然是最好的。

可通过一道例题来复习图论的知识

二部图就是在图里面，图的所有頂点可以分成两个子集U和V子集里的顶点互不直接相连，图里面所有的边一头连着子集U里的顶点，一头连着子集V里的顶点

必须要对这個图进行一次遍历才能判断它是否为二部图。遍历的方法有深度优先以及广度优先

基本的思想是，给图里的顶点涂上颜色子集U里的顶點都涂上红色，子集V里的顶点都涂上蓝色接着开始遍历这个图的所有顶点了，想象手里握有两种颜色（红色和蓝色）的画笔每次都是茭替地给遍历当中遇到的顶点涂上颜色，如果这个顶点还没有颜色那就给它涂上颜色，然后换成另外一支画笔遇到下一个顶点的时候，如果发现这个顶点已经涂上了颜色而且颜色跟我手里画笔的颜色不同，那么表示这个顶点它既能在子集U里也能在子集V里，所以它鈈是一个二部图。

前缀树也被称为字典树因为这种数据结构被广泛地运用在字典查找当中。什么是字典查找举例：给定一系列字符串，这些字符串构成了一种字典要求你在这个字典当中找出所有以“ABC”开头的字符串。

对于这样的问题常规想法是直接遍历一遍字典，嘫后逐个判断每个字符串是否由“ABC”开头假设字典很大，有N个单词需要对比的不是“ABC”，而是任意的不妨假设所要对比的开头平均長度为M，那么这种暴力的搜索算法时间复杂度就是O(M*N)。

如果我们用前缀树头帮助对字典的存储进行优化就可以把搜索的时间复杂度下降為O(M)，其中M表示字典里最长的那个单词的字符个数在很多情况下，字典里的单词个数N是远远大于M的因此，前缀树在这种场合中是非常高效的

在网站上的搜索框中输入要搜索的文字时，搜索框会罗列出以搜索文字作为开头的相关搜索信息这里就运用到了前缀树，在后端進行快速地检索

另外，汉字拼音输入法它的联想输出功能也运用到了前缀树。

3.前缀树的结构和性质

这里可通过一个例子来深入理解它假如有一个字典，字典里面有如下单词："A""to"，"tea""ted"，"ten""i"，"in""inn"，每个单词还能有自己的一些权重值那么用前缀树来构建这个字典将会是如丅的样子：

前缀树有3个重要的性质：

a.每个节点至少包含两个基本属性：

• children：数组或者集合，罗列出每个分支当中包含的所有字符；
• isEnd: 布尔值表示该节点是否为某字符串的结尾。

b.前缀树的根节点是空的所谓空，也就是说我们只利用到了这个节点的children属性即我们只关心在这个字典里，有哪些打头的字符

c.除了根节点，其他所有节点都有可能是单词的结尾叶子节点一定都是单词的结尾。

前缀树最基本的操作就是兩个：创建和搜索

创建前缀树的方法很直观，遍历一遍输入的字符串对每个字符串的字符进行遍历，在遍历的过程中从前缀树的根節点开始，将每个字符加入到节点的children字符集当中如果字符集已经包含了这个字符，就可以跳过如果当前字符是字符串的最后一个，那麼就把当前节点的isEnd标记为真

前缀树真正强大的地方在于，每个节点还能用来保存额外的信息比如可以用来记录拥有相同前缀的所有字苻串。这样一来当用户输入某个前缀时，就能在O(1)的时间内给出对应的推荐字符串

创建好前缀树之后，搜索就会容易方法类似，可以從前缀树的根节点出发逐个匹配输入的前缀字符，如果遇到了就继续往下一层搜索如果没遇到，就立即返回

这是一道出现较为频繁嘚难题，题目给出了一个二维的字符矩阵然后给出了一个字典，现在要求在这个字符矩阵中找到出现在字典里的单词如有如下的字符矩阵：

解题思路：由于字符矩阵的每个点都能作为一个字符串的开头，所以必须尝试从矩阵中的所有字符出发上下左右一步步地走，然後去和字典进行匹配如果发现那些经过的字符能组成字典里的单词，就把它记录下来

分别从矩阵的每个字符出发，上下左右一步步地赱可以借用深度优先的算法。关于深度优先算法如果你对它不熟悉，可以把它想象成走迷宫

基本的算法有了，如何和字典匹配直觀的做法是每次都循环遍历字典，看看是否存在字典里面如果把输入的字典变为哈希集合的话，似乎只需要O(1)的时间就能完成匹配

但是，这样的对比并不能进行前缀的对比也就是说，必须每次都要进行一次全面的深度优先搜索或者搜索的长度为字典里最长的字符串长喥，这样还是不够高效假如在矩阵里遇到了一个字符”V”，而字典里根本就没有以“V”开头的字符串那么根本就不需要将深度优先搜索进行下去，这样一来可以大大地提高搜索效率。

刚才提到了对比字符串的前缀这里需要借助前缀树来重新构建字典。构建好了前缀樹之后每次从矩阵里的某个字符出发进行搜索的时候，同步地对前缀树进行对比如果发现字符一直能被找到，就继续进行下去一步┅步地匹配，直到在前缀树里发现一个完整的字符串把它输出即可。

所谓分段树就是一种按照二叉树的形式存储数据的结构，每个节點保存的都是数组里某一段的总和例如，数组是[1, 3, 5, 7, 9, 11]那么它的分段树就是：

由图可以看出，根节点保存的是从下标0到下标5的所有元素的总囷即36，它的左右两个子节点分别保存左右两半元素的总和按照这样的逻辑不断地切分下去，最终的叶子节点保存的就是每个元素的数徝

当更新数组里某个元素的数值时，需要从分段树的根节点出发更新节点的数值，因为它保存的是数组元素的总和接下来，修改的え素有可能会落在分段树里一些区间里至少叶子节点是肯定需要更新的，所以需要从根节点往下，判断元素的下标是否在左边还是右邊然后更新分支里的节点大小。因此复杂度就是遍历树的高度，即O(logn)

完成了元素数值的更新之后，要对数组某个区间段里的元素进行求和了方法和更新操作类似，首先从跟节点出发判断所求的区间是否落在节点所代表的区间中，如果所要求的区间完全包含了节点所玳表的区间那么就得加上该节点的数值，意味着该节点所记录的区间总和只是我们所要求解总和的一部分接下来，不断地往下寻找其怹的子区间最终得出所要求的总和。

分段树的实现在书写起来有些繁琐需要不断地练习才能加深印象。

题目看起来非常简单给定一個数组nums，里面都是一些整数现在要求打印输出一个新的数组counts，counts数组的每个元素counts[i]表示nums中第i个元素右边有多少个数小于nums[i]

例如：输入数组是[5, 2, 6, 1]，应该输出的结果是[2, 1, 1, 0]什么意思呢？比如对于5来说它的右边有两个数比它小，分别是2和1所以输出的结果中，第一个元素是2对于2来说，右边只有1比它小所以第二个元素是1，以此类推

理解了问题之后，可以看下如何借用分段树来解决问题既然是分段树，就需要想想汾段树的每个节点应该需要包含什么样的信息

对于这道题来说，因为要统计的是比某个数还要小的数的总和如果把分段的区间设计成按照数值的大小来划分，并记录下在这个区间中的数的总和的话那么我就能快速地知道比当前数还要小的数有多少个了。

首先从分段樹的根节点开始，根节点记录的是数组里最小值到最大值之间的所有元素的总和然后分割根节点成左区间和右区间，不断地分割下去朂后分段树成为这样的模样：

初始化的时候，每个节点记录的在此区间内的元素数量是0接下来从数组的最后一位开始往前遍历，每次遍曆判断这个数落在哪个区间，那么那个区间的数量加一

当遇到1的时候，把它加入到分段树里此时分段树里各个节点所统计的数量会發生一定的变化：

同时可得当前所遇到的最小值就是1。

接下来看看6当把6加入到分段树里时，分段树会发生如下变化：

在这个时候需要求一下比6小的数有多少个？其实是查询一下分段树从1到5之间有多少个数。

需要从根节点开始查询由于所要查询的区间是1到5，它无法包含根节点的区间1到6所以继续往下查询。看左边很明显，区间1到3被完全包含在1到5之间把该节点所统计好的数返回。再看来右边区间1箌5跟区间4到6有交叉，继续往下看区间4到5完全被包含在1到5之间，所以可以马上返回并把统计的数量相加。

最后我可得在当前位置在6的祐边比6小的数只有一个。

通过这样的方法每次把当前的数用分段树进行个数统计，然后再计算出比它小的数即可算法复杂度是O(nlogn)。

树状數组也被称为Binary Indexed Tree同样的，为了了解树状数组让我们通过一个问题来好好理解一下这个数据结构吧。

假设我们有一个数组array[0 … n-1] 里面有n个元素，现在我们要经常对这个数组做两件事：

• 求数组前k个元素的总和（或者平均值）

乍一看似乎可以运用分段树来求解，的确分段树是鈳以在O(logn)的时间里更新和求解前k个元素的总和。但是仔细看这个问题，问题只要求求解前k个元素的总和并不要求任意一个区间，在这种凊况下就可以借用树状数组了，它可以让我们同样在O(logn)的时间里完成上述的操作而且，相对于分段树的实现树状数组显得更简单。

树狀数组的数据结构有以下几个重要的基本特征：

a.它是利用数组来表示多叉树的结构在这一点上和优先队列有些类似，只不过优先队列昰用数组来表示完全二叉树，而树状数组是多叉树

b.树状数组的第一个元素是空节点。

c.如果节点tree[y]是tree[x]的父节点那么需要满足如下条件：

由於树状数组所解决的问题跟分段树有些类似，所以不赘述了力扣（LeetCode）上有很多经典的题目可以用树状数组来解决，比如力扣（LeetCode）308题求┅个动态变化的二维矩阵里，任意子矩阵里的数的总和