第5章 优化时间和空间效率 5.1 面试官谈效率 “通常针对一些senior dev的candidates会问一些关于时间、空间效率的问题，这能够体现一个应聘者较好的编程素质和能力。” ——刘景勇（Autodesk，软件工程师） “面试时一般会直接要求空间和时间复杂度，这两者都很重要。” ——张珺（百度，高级软件工程师） “我们有很多考查时间、空间效率这方面的问题。通常两者都给应聘者限定，然后让他给出解决方案。” ——张晓禹（百度，技术经理） “只要不是特别大的内存开销，时间复杂度比较重要。因为改进时间复杂度对算法的要求更高。” ——吴斌（NVidia，Graphics Architect） “空间换时间还是时间换空间，这要看具体的题目了。对于普通的应用，一般是空间换时间，因为通常用户更关心速度，而且一般有足够的存储空间允许这么做。但对于现在的一般嵌入式设备，很多时候空间换时间就不现实了，因为存储空间太少了。” ——陈黎明（微软，SDE II） 5.2 时间效率 由于每个人都希望软件的响应时间尽量短一些，所以软件公司都很重视软件的时间性能，都会在发布软件之前花不少精力做时间效率优化。这也就不难理解为什么很多公司的面试官都把代码的时间效率当做一个考查重点。面试官除了考查应聘者的编程能力之外，还关注应聘者有没有不断优化效率、追求完美的态度和能力。 首先，我们的编程习惯对代码的时间效率有很大影响。比如C/C++程序员要养成采用引用（或指针）传递复杂类型参数的习惯。如果采用值传递的方式，从形参到实参会产生一次复制操作。这样的复制是多余的操作，我们应该尽量避免。再举个例子，如果用C#做多次字符串的拼接操作，不要多次用String的+运算符来拼接字符串，因为这样会产生很多String的临时实例，造成时间和空间的浪费。更好的办法是用StringBuilder的Append方法来完成字符串的拼接。如果我们平时不太注意这些影响代码效率的细节，没有养成好的编码习惯，那么我们的代码可能就会让面试官大失所望。 其次，即使同一个算法用循环和递归两种思路实现的时间效率可能会大不一样。递归的本质是把一个大的复杂问题分解成两个或者多个小的简单的问题。如果小问题中有相互重叠的部分，那么直接用递归实现虽然代码显得很简洁，但时间效率可能会非常差（详细讨论见本书2.4.2节）。对于这种类型的题目，我们可以用递归的思路来分析问题，但写代码的时候可以用数组（一维或者多维数组）来保存中间结果基于循环实现。绝大部分动态规划算法的分析和代码实现都是分这两个步骤完成的。 再次，代码的时间效率还能体现应聘者对数据结构和算法功底的掌握程度。同样是查找，如果是顺序查找需要O（n）的时间；如果输入的是排序的数组则只需要O（logn）的时间；如果事先已经构造好了哈希表，那查找在O（1）时间就能完成。我们只有对常见的数据结构和算法都了然于胸，才能在需要的时候选择合适的数据结构和算法来解决问题。 最后，应聘者在面试的时候要展示敏捷的思维能力和追求完美的激情。听到题目的时候，我们一般很快就能想到最直观的算法。这个最直观的办法很有可能不是最优的，但也不妨在第一时间告诉面试官，这样面试官至少会觉得我们思维比较敏捷。我们想到几种思路之后面试官可能仍然不满意，还在提示我们有更好的办法。这个时候我们一定不能轻言放弃，而要表现出积极思考的态度，努力从不同的角度去思考问题。有些题目很难，面试官甚至不期待应聘者在短短几十分钟里想出完美的解法，但他会希望应聘者能够有激情、有耐心去尝试新的思路，而不是碰到难题就退缩。在面试的时候，应聘者的态度和激情对最终的面试结果也有很重要的影响。 面试题29：数组中出现次数超过一半的数字 题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。 看到这道题很多应聘者就会想要是这个数组是排序的数组就好了。如果是排好序的数组，那么我们就能很容易统计出每个数字出现的次数。题目给出的数组没有说是排序的，因此我们需要先给它排序。排序的时间复杂度是O（nlogn）。最直观的算法通常不是面试官满意的算法，接下来我们试着找出更快的算法。 解法一：基于Partition函数的O（n）算法 如果我们回到题目本身仔细分析，就会发现前面的思路并没有考虑到数组的特性：数组中有一个数字出现的次数超过了数组长度的一半。如果把这个数组排序，那么排序之后位于数组中间的数字一定就是那个出现次数超过数组长度一半的数字。也就是说，这个数字就是统计学上的中位数，即长度为n的数组中第n/2大的数字。我们有成熟的O（n）的算法得到数组中任意第k大的数字。 这种算法是受快速排序算法的启发。在随机快速排序算法中，我们先在数组中随机选择一个数字，然后调整数组中数字的顺序，使得比选中的数字小数字都排在它的左边，比选中的数字大的数字都排在它的右边。如果这个选中的数字的下标刚好是n/2，那么这个数字就是数组的中位数。如果它的下标大于n/2，那么中位数应该位于它的左边，我们可以接着在它的左边部分的数组中查找。如果它的下标小于n/2，那么中位数应该位于它的右边，我们可以接着在它的右边部分的数组中查找。这是一个典型的递归过程，可以用如下代码实现：  上述代码中的函数Partition是完成快速排序的基础。我们在本书的2.4.1节详细讨论了这个函数，这里不再重复。 在面试的时候，除了要完成基本功能即找到符合要求的数字之外，还要考虑一些无效的输入。如果函数的输入参数是一个指针（数组在参数传递的时候退化为指针），就要考虑这个指针可能为NULL。下面的函数CheckInvalidArray用来判断输入的数组是不是无效的。题目中说数组中有一个数字出现次数超过数组长度的一半，如果输入的数组中出现频率最高的数字都没有达到这个标准那该怎么办？这就是我们定义了一个CheckMoreThanHalf函数的原因。面试的时候我们要全面考虑这些情况，才能让面试官完全满意。下面的代码用一个全局变量来表示输入无效的情况。更多关于出错处理的讨论，详见本书3.3节。  解法二：根据数组特点找出O（n）的算法 接下来我们从另外一个角度来解决这个问题。数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现次数的和还要多。因此我们可以考虑在遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为零，我们需要保存下一个数字，并把次数设为1。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时对应的数字。 下面是这种思路的参考代码：  和第一种思路一样，我们也要检验输入的数组是不是有效的，这里不再重复。 解法比较 上述两种算法的时间复杂度都是O（n）。基于Partition的算法的时间复杂度的分析不是很直观，本书限于篇幅不作详细讨论，感兴趣的读者可以参考《算法导论》等书籍的相关章节。我们注意到在第一个解法中，需要交换数组中数字的顺序，这就会修改输入的数组。我们是不是可以修改输入的数组呢？在面试的时候，我们可以和面试官讨论，让他明确需求。如果面试官说不能修改输入的数组，那就只能采用第二种算法了。 源代码： 本题完整的源代码详见29\_MoreThanHalfNumber项目。 测试用例： ● 功能测试（输入的数组中存在一个出现次数超过数组长度一半的数字，输入的数组中不存在一个出现次数超过数组长度一半的数字）。 ● 特殊输入测试（输入的数组中只有一个数字、输入NULL指针）。 本题考点： ● 考查对时间复杂度的理解。应聘者每想出一种解法，面试官都期待他能分析出这种解法的时间复杂度是多少。 ● 考查思维的全面性。面试官除了要求应聘者能对有效的输入返回正确的结果之外，同时也期待应聘者能对无效的输入作相应的处理。 面试题30：最小的k个数 题目：输入n个整数，找出其中最小的k个数。例如输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 这道题最简单的思路莫过于把输入的n个整数排序，排序之后位于最前面的k个数就是最小的k个数。这种思路的时间复杂度是O（nlogn），面试官会提示我们还有更快的算法。 解法一：O（n）的算法，只有当我们可以修改输入的数组时可用 从解决面试题29“数组中出现次数超过一半的数字”得到了启发，我们同样可以基于Partition函数来解决这个问题。如果基于数组的第k个数字来调整，使得比第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组的右边。这样调整之后，位于数组中左边的k个数字就是最小的k个数字（这k个数字不一定是排序的）。下面是基于这种思路的参考代码：  采用这种思路是有限制的。我们需要修改输入的数组，因为函数Partition会调整数组中数字的顺序。如果面试官要求不能修改输入的数组，我们该怎么办呢？ 解法二：O（nlogk）的算法，特别适合处理海量数据 我们可以先创建一个大小为k的数据容器来存储最小的k个数字，接下来我们每次从输入的n个整数中读入一个数。如果容器中已有的数字少于k个，则直接把这次读入的整数放入容器之中；如果容器中已有k个数字了，也就是容器已满，此时我们不能再插入新的数字而只能替换已有的数字。找出这已有的k个数中的最大值，然后拿这次待插入的整数和最大值进行比较。如果待插入的值比当前已有的最大值小，则用这个数替换当前已有的最大值；如果待插入的值比当前已有的最大值还要大，那么这个数不可能是最小的k个整数之一，于是我们可以抛弃这个整数。 因此当容器满了之后，我们要做3件事情：一是在k个整数中找到最大数；二是有可能在这个容器中删除最大数；三是有可能要插入一个新的数字。如果用一个二叉树来实现这个数据容器，那么我们能在O（logk）时间内实现这三步操作。因此对于n个输入数字而言，总的时间效率就是O（nlogk）。 我们可以选择用不同的二叉树来实现这个数据容器。由于每次都需要找到k个整数中的最大数字，我们很容易想到用最大堆。在最大堆中，根结点的值总是大于它的子树中任意结点的值。于是我们每次可以在O（1）得到已有的k个数字中的最大值，但需要O（logk）时间完成删除及插入操作。 我们自己从头实现一个最大堆需要一定的代码，这在面试短短的几十分钟内很难完成。我们还可以采用红黑树来实现我们的容器。红黑树通过把结点分为红、黑两种颜色并根据一些规则确保树在一定程度上是平衡的，从而保证在红黑树中查找、删除和插入操作都只需要O（logk）时间。在STL中set和multiset都是基于红黑树实现的。如果面试官不反对我们用STL中的数据容器，我们就可以直接拿过来用。下面是基于STL中的multiset的参考代码：  解法比较 基于函数Partitiaon的第一种解法的平均时间复杂度是O（n），比第二种思路要快，但同时它也有明显的限制，比如会修改输入的数组。 第二种解法虽然要慢一点，但它有两个明显的优点。一是没有修改输入的数据（代码中的变量data）。我们每次只是从data中读入数字，所有的写操作都是在容器leastNumbers中进行的。二是该算法适合海量数据的输入（包括百度在内的多家公司非常喜欢与海量输入数据相关的问题）。假设题目是要求从海量的数据中找出最小的k个数字，由于内存的大小是有限的，有可能不能把这些海量的数据一次性全部载入内存。这个时候，我们可以从辅助存储空间（比如硬盘）中每次读入一个数字，根据GetLeastNumbers的方式判断是不是需要放入容器leastNumbers即可。这种思路只要求内存能够容纳leastNumbers即可，因此它最适合的情形就是n很大并且k较小的问题。 我们可以用表5.1总结这两种解法的特点。 表5.1 两种算法的特点比较  由于这两种算法各有优缺点，各自适用于不同的场合，因此应聘者在动手做题之前先要问清楚题目的要求，包括输入的数据量有多大、能否一次性载入内存、是否允许交换输入数据中数字的顺序等。 面试小提示： 如果面试时遇到的面试题有多种解法，并且每个解法都各有优缺点，那么我们要向面试官问清楚题目的要求，输入的特点，从而选择最合适的解法。 源代码： 本题完整的源代码详见30\_KLeastNumbers项目。 测试用例： ● 功能测试（输入的数组中有相同的数字，输入的数组中没有相同的数字）。 ● 边界值测试（输入的k等于1或者等于数组的长度） ● 特殊输入测试（k小于1、k大于数组的长度、指向数组的指针为NULL）。 本题考点： ● 考查对时间复杂度的分析能力。面试的时候每想出一个解法，我们都要能分析出这种解法的时间复杂度是多少。 ● 如果采用第一种思路，本题考查对Partition函数的理解。这个函数既是快速排序的基础，也可以用来查找n个数中第k大的数字。 ● 如果采用第二种思路，本题考查对堆、红黑树等数据结构的理解。当需要在某数据容器内频繁查找及替换最大值时，我们要想到二叉树是个合适的选择，并能想到用堆或者红黑树等特殊的二叉树来实现。 面试题31：连续子数组的最大和 题目：输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O（n）。 例如输入的数组为{1,-2,3,10,-4,7,2,-5}，和最大的子数组为{3,10,-4,7,2}，因此输出为该子数组的和18。 看到这道题，很多人都能想到最直观的方法，即枚举出数组的所有子数组并求出它们的和。一个长度为n的数组，总共有n（n＋1）/2个子数组。计算出所有子数组的和，最快也需要O（n2）的时间。通常最直观的方法不会是最优的解法，面试官将提示我们还有更快的算法。 解法一：举例分析数组的规律 我们试着从头到尾逐个累加示例数组中的每个数字。初始化和为0。第一步加上第一个数字1，此时和为1。接下来第二步加上数字-2，和就变成了-1。第三步加上数字3。我们注意到由于此前累计的和是-1，小于0，那如果用-1加上3，得到的和是2，比3本身还小。也就是说从第一个数字开始的子数组的和会小于从第三个数字开始的子数组的和。因此我们不用考虑从第一个数字开始的子数组，之前累计的和也被抛弃。 我们从第三个数字重新开始累加，此时得到的和是3。接下来第四步加10，得到和为13。第五步加上-4，和为9。我们发现由于-4是一个负数，因此累加-4之后得到的和比原来的和还要小。因此我们要把之前得到的和13保存下来，它有可能是最大的子数组的和。第六步加上数字7，9加7的结果是16，此时和比之前最大的和13还要大，把最大的子数组的和由13更新为16。第七步加上2，累加得到的和为18，同时我们也要更新最大子数组的和。第八步加上最后一个数字-5，由于得到的和为13，小于此前最大的和18，因此最终最大的子数组的和为18，对应的子数组是{3,10,-4,7,2}。整个过程可以用表5.2总结如下： 表5.2 计算数组{1,-2,3,10,-4,7,2,-5}中子数组的最大和的过程  把过程分析清楚之后，我们就可以动手写代码了。下面是一段参考代码：  面试的时候我们要考虑无效的输入，比如输入的数组参数为空指针、数组长度小于等于0等情况。此时我们让函数返回什么数字？如果是返回0，那我们又怎么区分子数组的和的最大值是0和无效输入这两种不同情况呢？因此我们定义了一个全局变量来标记是否输入无效。 解法二：应用动态规划法 如果算法的功底足够扎实，我们还可以用动态规划的思想来分析这个问题。如果用函数f（i）表示以第i个数字结尾的子数组的最大和，那么我们需要求出max\[f（i）\]，其中0≤i<n。我们可用如下递归公式求f（i）：  这个公式的意义：当以第i－1个数字结尾的子数组中所有数字的和小于0时，如果把这个负数与第i个数累加，得到的结果比第i个数字本身还要小，所以这种情况下以第i个数字结尾的子数组就是第i个数字本身（如表5.2的第3步）。如果以第i－1个数字结尾的子数组中所有数字的和大于0，与第i个数字累加就得到以第i个数字结尾的子数组中所有数字的和。 虽然通常我们用递归的方式分析动态规划的问题，但最终都会基于循环去编码。上述公式对应的代码和前面给出的代码一致。递归公式中的f（i）对应的变量是nCurSum，而max\[f（i）\]就是nGreatestSum。因此可以说这两种思路是异曲同工。 源代码： 本题完整的源代码详见31\_GreatestSumOfSubarrays项目。 测试用例： ● 功能测试（输入的数组中有正数也有负数，输入的数组中全是正数，输入的数组中全是负数）。 ● 特殊输入测试（表示数组的指针为NULL指针）。 本题考点： ● 考查对时间复杂度的理解。这道题如果应聘者给出时间复杂度为O（n2）甚至O（n3）的算法，是不能通过面试的。 ● 考查对动态规划的理解。如果应聘者熟练掌握了动态规划算法，那么他就能轻松地找到解题方案。如果没有想到用动态规划的思想，那么应聘者就需要仔细地分析累加子数组的和的过程，从而找到解题的规律。 ● 考查思维的全面性。能否合理地处理无效的输入，对面试结果有很重要的影响。 面试题32：从1到n整数中1出现的次数 题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。 不考虑时间效率的解法，靠它想拿Offer有点难 如果在面试的时候碰到这个问题，应聘者大多能想到最直观的方法，也就是累加1到n中每个整数1出现的次数。我们可以每次通过对10求余数判断整数的个位数字是不是1。如果这个数字大于10，除以10之后再判断个位数字是不是1。基于这个思路，我们不难写出如下代码：  在上述思路中，我们对每个数字都要做除法和求余运算以求出该数字中1出现的次数。如果输入数字n，n有O（logn）位，我们需要判断每一位是不是1，那么它的时间复杂度是O（n\*logn）。当输入n非常大的时候，需要大量的计算，运算效率不高。面试官不会满意这种算法，我们仍然需要努力。 从数字规律着手明显提高时间效率的解法，能让面试官耳目一新 如果希望不用计算每个数字的1的个数，那就只能去寻找1在数字中出现的规律了。为了找到规律，我们不妨用一个稍微大一点的数字比如21345作为例子来分析。我们把从1到21345的所有数字分为两段，一段是从1到1345，另一段是从1346到21345。 我们先看从1346到21345中1出现的次数。1的出现分为两种情况。首先分析1出现在最高位（本例中是万位）的情况。从1346到21345的数字中，1出现在10000～19999这10000个数字的万位中，一共出现了10000（104）个。 值得注意的是，并不是对所有5位数而言在万位出现的次数都是10000个。对于万位是1的数字比如输入12345，1只出现在10000～12345的万位，出现的次数不是104次，而是2346次，也就是除去最高数字之后剩下的数字再加上1（即2345＋1=2346次）。 接下来分析1出现在除最高位之外的其他四位数中的情况。例子中1346～21345这20000个数字中后4位中1出现的次数是2000次。由于最高位是2，我们可以再把1346～21345分成两段，1346～11345和11346～21345。每一段剩下的4位数字中，选择其中一位是1，其余三位可以在0～9这10个数字中任意选择，因此根据排列组合原则，总共出现的次数是2×103=2000次。 至于从1到1345中1出现的次数，我们就可以用递归求得了。这也是我们为什么要把1～21345分成1～1345和1346～21345两段的原因。因为把21345的最高位去掉就变成1345，便于我们采用递归的思路。 基于前面的分析，我们可以写出如下代码（为了编程方便，我们先把数字转换成字符串）：  这种思路是每次去掉最高位做递归，递归的次数和位数相同。一个数字n有O（logn）位，因此这种思路的时间复杂度是O（logn），比前面的原始方法要好很多。 源代码： 本题完整的源代码详见32\_NumberOf1项目。 测试用例： ● 功能测试（输入5、10、55、99等）。 ● 边界值测试（输入0、1等）。 ● 性能测试（输入较大的数字如10000、21235等）。 本题考点： ● 考查应聘者做优化的激情和能力。最原始的方法大部分应聘者都能想到。当面试官提示还有更快的方法之后，应聘者千万不要轻易放弃尝试。虽然想出O（logn）的方法不容易，但应聘者要展示自己追求更快算法的激情，多尝试不同的方法，必要的时候可以要求面试官给出提示，但不能轻易说自己想不出来并且放弃努力。 ● 考查面应聘者对复杂问题的思维能力。要想找到O（logn）的方法，应聘者需要有很严密的数学思维能力，并且还要通过分析具体例子一步步找到通用的规律。这些能力在实际工作中面对复杂问题的时候都非常有用。 面试题33：把数组排成最小的数 题目：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321}，则打印出这3个数字能排成的最小数字321323。 这个题目最直接的做法应该是先求出这个数组中所有数字的全排列，然后把每个排列拼起来，最后求出拼起来的数字的最大值。求数组的排列和面试题28“字符串的排列”非常类似，这里不再详细介绍。根据排列组合的知识，n个数字总共有n!个排列。我们再来看一种更快的算法。 这道题其实是希望我们能找到一个排序规则，数组根据这个规则排序之后能排成一个最小的数字。要确定排序规则，就要比较两个数字，也就是给出两个数字m和n，我们需要确定一个规则判断m和n哪个应该排在前面，而不是仅仅比较这两个数字的值哪个更大。 根据题目的要求，两个数字m和n能拼接成数字mn和nm。如果mn<nm，那么我们应该打印出mn，也就是m应该排在n的前面，我们定义此时m小于n；反之，如果nm<mn，我们定义n小于m。如果mn=nm，m等于n。在下文中，符号“<”、“>”及“=”表示常规意义的数值的大小关系，而文字“大于”、“小于”、“等于”表示我们新定义的大小关系。 接下来考虑怎么去拼接数字，即给出数字m和n，怎么得到数字mn和nm并比较它们的大小。直接用数值去计算不难办到，但需要考虑到一个潜在的问题就是m和n都在int能表达的范围内，但把它们拼起来的数字mn和nm用int表示就有可能溢出了，所以这还是一个隐形的大数问题。 一个非常直观的解决大数问题的方法就是把数字转换成字符串。另外，由于把数字m和n拼接起来得到mn和nm，它们的位数肯定是相同的，因此比较它们的大小只需要按照字符串大小的比较规则就可以了。 基于这个思路，我们可以写出如下代码：  在上述代码中，我们先把数组中的整数转换成字符串，在函数compare中定义比较规则，并根据该规则用库函数qsort排序。最后把排好序的数组中的数字依次打印出来，就是该数组中数字能拼接出来的最小数字。这种思路的时间复杂度和qsort的时间复杂度相同，也就是O（nlogn），这比用n!的时间求出所有排列的思路要好很多。 上述思路中，我们定义了一种新的比较两个数的规则，这种规则是不是有效的？另外，我们只是定义了比较两个数的规则，却用它来排序一个含有多个数字的数组，最终拼接数组中的所有数字得到的是不是真的就是最小的数字？一些严格的面试官还会要求我们给出严格的数学证明，以确保我们的解决方案是正确的。 我们首先证明之前定义的比较两个数字大小的规则是有效的。一个有效的比较规则需要3个条件：自反性、对称性和传递性。我们分别予以证明。 （1）自反性：显然有aa=aa，所以a等于a。 （2）对称性：如果a小于b，则ab<ba，所以ba>ab，因此b大于a。 （3）传递性：如果a小于b，则ab<ba。假设a和b用十进制表示时分别有l位和m位，于是ab=a×10m＋b，ba=b×10l＋a。 ab<ba→a×10m＋b<b×10l＋a→a×10m－a< b×10l－b →a（10m－1）<b（10l－1）→a/（10l－1）<b/（10m－1） 同时如果b小于c，则bc<cb。假设c用十进制表示是有n位，和前面的证明过程一样，可以得到b/（10m－1）<c/（10n－1）。 a/（10l－1）<b/（10m－1）并且b/（10m－1）<c/（10n－1）→a/（10l－1）<c/（10n－1）→a（10n－1）<c（10l－1） →a×10n＋c<c×10l＋a→ac<ca→a小于c 于是我们证明了这种比较规则满足自反性、对称性和传递性，是一种有效的比较规则。接下来我们证明根据这种比较规则把数组排序之后，把数组中的所有数字拼接起来得到的数字的确是最小的。直接证明不是很容易，我们不妨用反证法来证明。 我们把n个数按照前面的排序规则排序之后，表示为A1A2A3…An。假设这样拼接出来的数字并不是最小的，即至少存在两个x和y（0<x<y<n），交换第x个数和第y个数后，A1A2…Ay…Ax…An<A1A2…Ax…Ay…An。 由于A1A2…Ax…Ay…An是按照前面的规则排好的序列，所以有Ax小于Ax＋1小于Ax＋2小于…小于Ay－2小于Ay－1小于Ay。 由于Ay－1小于Ay，所以Ay－1Ay<AyAy－1。我们在序列A1A2…Ax…Ay－1Ay…An中交换Ay－1和Ay，有A1A2…Ax…Ay－1Ay…An<A1A2…Ax…AyAy－1…An（这个实际上也需要证明，感兴趣的读者可以自己试着证明）。我们就这样一直把Ay和前面的数字交换，直到和Ax交换为止。于是就有A1A2…Ax…Ay－1Ay…An<A1A2…Ax…AyAy－1…An<A1A2…Ax…AyAy－2Ay－1…An<…<A1A2…AyAx…Ay－2Ay－1…An。 同理由于Ax小于Ax＋1，所以AxAx＋1<Ax＋1Ax。我们在序列A1A2…AyAxAx＋1…Ay－2Ay－1…An中只交换Ax和Ax＋1，有A1A2…AyAxAx＋1…Ay－2Ay－1…An<A1A2…AyAx＋1Ax…Ay－2Ay－1…An。我们接下来一直拿Ax和它后面的数字交换，直到和Ay－1交换为止。于是就有A1A2…AyAxAx＋1…Ay－2Ay－1…An<A1A2…AyAx＋1Ax…Ay－2Ay－1…An<…<A1A2…AyAx＋1Ax＋2…Ay－2Ay－1Ax…An。 所以A1A2…Ax…Ay…An<A1A2…Ay…Ax…An，这和我们的假设的A1A2…Ay…Ax…An<A1A2…Ax…Ay…An相矛盾。 所以假设不成立，我们的算法是正确的。 源代码： 本题完整的源代码详见33\_SortArrayForMinNumber项目。 测试用例： ● 功能测试（输入的数组中有多个数字，输入的数组中的数字有重复的数位，输入的数字只有一个数字）。 ● 特殊输入测试（表示数组的指针为NULL指针）。 本题考点： ● 本题有两个难点；第一个难点是想出一种新的比较规则来排序一个数组；第二个难点在于证明这个比较规则是有效的，并且证明根据这个规则排序之后把数组中所有数字拼接起来得到的数字是最小的。要想解决这两个难点，都要求应聘者有很强的数学功底和逻辑思维能力。 ● 考查解决大数问题的能力。应聘者在面试的时候要意识到，把两个int型的整数拼接起来得到的数字可能会超出int型数字能够表达的范围，从而导致数字溢出。我们可以用字符串表示数字，这样就能简洁地解决大数问题。 5.3 时间效率与空间效率的平衡 硬件的发展一直遵循着摩尔定律，内存的容量基本上每隔18个月就会翻一番。由于内存的容量增加迅速，在软件开发的过程中我们允许以牺牲一定的空间为代码来优化时间性能，以尽可能地缩短软件的响应时间。这就是我们通常所说的“以空间换时间”。 在面试的时候，如果我们分配少量的辅助空间来保存计算的中间结果以提高时间效率，这样的思路通常是可以接受的。本书中收集的面试题中有不少这种类型的题目，比如在面试题34“丑数”中用一个数组按照从小到大的顺序保存已经求出的丑数；在面试题43“n个骰子的点数”中交替使用两个数组求骰子每个点数出现的次数。 值得注意的是，“以时间换空间”的策略并不一定都是可行的，在面试的时候要具体问题具体分析。我们都知道在n个无序的元素里做查找操作，需要O（n）的时间。但如果我们把这些元素放进一个哈希表，那么在哈希表内就能实现O（1）的查找。但同时实现一个哈希表是有空间消耗的，是不是值得以多消耗空间为前提来换取时间性能的提升，我们需要根据实际情况仔细权衡。在面试题35“第一个只出现一次的字符”中，我们用数组实现了一个简易哈希表，有了这个哈希表就能实现O（1）查找任意字符。对于ASCII码的字符而言，总共只有256个字符，因此只需要1K的辅助内存。这点内存消耗对于绝大多数硬件来说是完全可以接受的。但如果是16位的Unicode的字符，创建这样一个长度为216的整型数组需要4×216也就是256K的内存。这对于个人电脑来说也是可以接受的，但对于一些嵌入式的开发就要慎重了。 很多时候时间效率和空间效率存在类似于鱼与熊掌的关系，我们需要在它们之间有所取舍。在面试的时候究竟是“以时间换空间”还是“以空间换时间”，我们可以和面试官进行探讨。多和面试官进行这方面的讨论是很有必要的，这既能显示我们的沟通能力，又能展示我们对软件性能全方位的把握能力。 面试题34：丑数 题目：我们把只包含因子2、3和5的数称作丑数（Ugly Number）。求按从小到大的顺序的第1500个丑数。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做第一个丑数。 逐个判断每个整数是不是丑数的解法，直观但不够高效 所谓一个数m是另一个数n的因子，是指n能被m整除，也就是n%m＝0。根据丑数的定义，丑数只能被2、3和5整除。也就是说如果一个数能被2整除，我们把它连续除以2；如果能被3整除，就连续除以3；如果能被5整除，就除以连续5。如果最后我们得到的是1，那么这个数就是丑数，否则不是。 因此我们可以写出下面的函数来判断一个数是不是丑数：  接下来，我们只需要按照顺序判断每一个整数是不是丑数，即：  我们只需要在函数GetUglyNumber中传入参数1500，就能得到第1500个丑数。该算法非常直观，代码也非常简洁，但最大的问题每个整数都需要计算。即使一个数字不是丑数，我们还是需要对它做求余数和除法操作。因此该算法的时间效率不是很高，面试官也不会就此满足，他会提示我们还有更高效的算法。 创建数组保存已经找到的丑数，用空间换时间的解法 前面的算法之所以效率低，很大程度上是因为不管一个数是不是丑数我们对它都要作计算。接下来我们试着找到一种只要计算丑数的方法，而不在非丑数的整数上花费时间。根据丑数的定义，丑数应该是另一个丑数乘以2、3或者5的结果（1除外）。因此我们可以创建一个数组，里面的数字是排好序的丑数，每一个丑数都是前面的丑数乘以2、3或者5得到的。 这种思路的关键在于怎样确保数组里面的丑数是排好序的。假设数组中已经有若干个丑数排好序后存放在数组中，并且把已有最大的丑数记做M，我们接下来分析如何生成下一个丑数。该丑数肯定是前面某一个丑数乘以2、3或者5的结果，所以我们首先考虑把已有的每个丑数乘以2。在乘以2的时候，能得到若干个小于或等于M的结果。由于是按照顺序生成的，小于或者等于M肯定已经在数组中了，我们不需再次考虑；还会得到若干个大于M的结果，但我们只需要第一个大于M的结果，因为我们希望丑数是按从小到大的顺序生成的，其他更大的结果以后再说。我们把得到的第一个乘以2后大于M的结果记为M2。同样，我们把已有的每一个丑数乘以3和5，能得到第一个大于M的结果M3和M5。那么下一个丑数应该是M2、M3和M5这3个数的最小者。 前面分析的时候，提到把已有的每个丑数分别都乘以2、3和5。事实上这不是必须的，因为已有的丑数是按顺序存放在数组中的。对乘以2而言，肯定存在某一个丑数T2，排在它之前的每一个丑数乘以2得到的结果都会小于已有最大的丑数，在它之后的每一个丑数乘以2得到的结果都会太大。我们只需记下这个丑数的位置，同时每次生成新的丑数的时候，去更新这个T2。对乘以3和5而言，也存在着同样的T3和T5。 有了这些分析，我们就可以写出如下代码：  和第一种思路相比，第二种思路不需要在非丑数的整数上做任何计算，因此时间效率有明显提升。但也需要指出，第二种算法由于需要保存已经生成的丑数，因此需要一个数组，从而增加了空间消耗。如果是求第1500个丑数，将创建一个能容纳1500个丑数的数组，这个数组占内存6KB。而第一种思路没有这样的内存开销。总的来说，第二种思路相当于用较小的空间消耗换取了时间效率的提升。 源代码： 本题完整的源代码详见34\_UglyNumber项目。 测试用例： ● 功能测试（输入2、3、4、5、6等）。 ● 特殊输入测试（边界值1、无效输入0）。 ● 性能测试（输入较大的数字，如1500）。 本题考点： ● 考查应聘者对时间复杂度的理解。绝大部分应聘者都能想出第一种思路。在面试官提示还有更快的解法之后，应聘者能否分析出时间效率的瓶颈，并找出解决方案，是能否通过这轮面试的关键。 ● 考查应聘者的学习能力和沟通能力。丑数对很多人而言是个新概念。有些面试官喜欢在面试的时候定义一个新概念，然后针对这个新概念出面试题。这就要求应聘者听到不熟悉的概念之后，要有主动积极的态度，大胆向面试官提问，经过几次思考、提问、再思考的循环，在短时间内理解这个新概念。这个过程就体现了应聘者的学习能力和沟通能力。 面试题35：第一个只出现一次的字符 题目：在字符串中找出第一个只出现一次的字符。如输入"abaccdeff"，则输出'b'。 看到这道题时，我们最直观的想法是从头开始扫描这个字符串中的每个字符。当访问到某字符时拿这个字符和后面的每个字符相比较，如果在后面没有发现重复的字符，则该字符就是只出现一次的字符。如果字符串有n个字符，每个字符可能与后面的O（n）个字符相比较，因此这种思路的时间复杂度是O（n2）。面试官不会满意这种思路，他会提示我们还有更快的方法。 由于题目与字符出现的次数相关，我们是不是可以统计每个字符在该字符串中出现的次数？要达到这个目的，我们需要一个数据容器来存放每个字符的出现次数。在这个数据容器中可以根据字符来查找它出现的次数，也就是说这个容器的作用是把一个字符映射成一个数字。在常用的数据容器中，哈希表正是这个用途。 为了解决这个问题，我们可以定义哈希表的键值（Key）是字符，而值（Value）是该字符出现的次数。同时我们还需要从头开始扫描字符串两次。第一次扫描字符串时，每扫描到一个字符就在哈希表的对应项中把次数加1。接下来第二次扫描时，每扫描到一个字符就能从哈希表中得到该字符出现的次数。这样第一个只出现一次的字符就是符合要求的输出。 哈希表是一种比较复杂的数据结构，并且C++的标准模板库中没有实现哈希表。接下来我们要考虑的问题就是如何实现哈希表。由于本题的特殊性，我们只需要一个非常简单的哈希表就能满足要求。字符（char）是一个长度为8的数据类型，因此总共有256 种可能。于是我们创建一个长度为256的数组，每个字母根据其ASCII码值作为数组的下标对应数组的一个数字，而数组中存储的是每个字符出现的次数。这样我们就创建了一个大小为256，以字符ASCII码为键值的哈希表。 第一次扫描时，在哈希表中更新一个字符出现的次数的时间是O（1）。如果字符串长度为n，那么第一次扫描的时间复杂度是O（n）。第二次扫描时，同样O（1）能读出一个字符出现的次数，所以时间复杂度仍然是O（n）。这样算起来，总的时间复杂度是O（n）。同时，我们需要一个包含256个字符的辅助数组，它的大小是1K。由于这个数组的大小是个常数，因此可以认为这种算法的空间复杂度是O（1）。 当我们向面试官讲述清楚这个思路并得到面试官的首肯之后，就可以动手写代码了。下面是一段参考代码：  源代码： 本题完整的源代码详见35\_FirstNotRepeatingChar项目。 测试用例： ● 功能测试（字符串中存在只出现一次的字符，字符串中不存在只出现一次字符，字符串中所有字符都只出现一次）。 ● 特殊输入测试（字符串为NULL指针）。 本题考点： ● 考查对数组、字符串的编程能力。 ● 考查对哈希表的理解及运用。 ● 考查对时间效率及空间效率的分析能力。当面试官提示最直观的算法不是最优解的时候，应聘者需要立即分析出这种算法的时间效率。在想出基于哈希表的算法之后，应聘者也应该分析出该方法的时间效率和空间效率分别是O（n）和O（1）。 本题扩展： 在前面的例子中，我们之所以可以把哈希表的大小设为256，是因为字符（char）是8个bit的类型，总共只有256个字符。但实际上字符不只是256个，比如中文就有几千个汉字。如果题目要求考虑汉字，前面的算法是不是有问题？如果有，可以怎么解决？ 相关题目： ● 定义一个函数，输入两个字符串，从第一个字符串中删除在第二个字符串中出现过的所有字符。例如从第一个字符串"We are students."中删除在第二个字符串"aeiou"中出现过的字符得到的结果是"W r Stdnts. "。为了解决这个问题，我们可以创建一个用数组实现的简单哈希表来存储第二个字符串。这样我们从头到尾扫描第一个字符串的每一个字符时，用O（1）时间就能判断出该字符是不是在第二个字符中。如果第一个字符串的长度是n，那么总的时间复杂度是O（n）。 ● 定义一个函数，删除字符串中所有重复出现的字符。例如输入"google"，删除重复的字符之后的结果是"gole"。这个题目和上面的问题比较类似，我们可以创建一个用布尔型数组实现的简单的哈希表。数组中的元素的意义是其下标看做ASCII码后对应的字母在字符串中是否已经出现。我们先把数组中所有的元素都设为false。以"google"为例，当扫描到第一个g时，g的ASCII码是103，那么我们把数组中下标为103的元素设为true。当扫描到第二个g时，我们发现数组中下标为103的元素的值是true，就知道g在前面已经出现了。也就是说，我们用O（1）时间就能判断出每个字符是否在前面已经出现过。如果字符串的长度是n，那么总的时间复杂度是O（n）。 ● 在英语中，如果两个单词中出现的字母相同，并且每个字母出现的次数也相同，那么这两个单词互为变位词（Anagram）。例如silent与listen、evil与live等互为变位词。请完成一个函数，判断输入的两个字符串是不是互为变位词。我们可以创建一个用数组实现的简单哈希表，用来统计字符串中每个字符出现的次数。当扫描到第一个字符串中的每个字符时，为哈希表对应的项的值增加1。接下来扫描第二个字符串，扫描到每个字符时，为哈希表对应的项的值减去1。如果扫描完第二个字符串后，哈希表中所有的值都是0，那么这两个字符串就互为变位词。 举一反三： 如果需要判断多个字符是不是在某个字符串里出现过或者统计多个字符在某个字符串中出现的次数，我们可以考虑基于数组创建一个简单的哈希表。这样可以用很小的空间消耗换来时间效率的提升。 面试题36：数组中的逆序对 题目：在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 例如在数组{7,5,6,4}中，一共存在5个逆序对，分别是（7,6）、（7,5）、（7,4）、（6,4）和（5,4）。 看到这个题目，我们的第一反应是顺序扫描整个数组。每扫描到一个数字的时候，逐个比较该数字和它后面的数字的大小。如果后面的数字比它小，则这两个数字就组成了一个逆序对。假设数组中含有n个数字。由于每个数字都要和O（n）个数字作比较，因此这个算法的时间复杂度是O（n2）。我们再尝试找找更快的算法。 我们以数组{7,5,6,4}为例来分析统计逆序对的过程。每次扫描到一个数字的时候，我们不能拿它和后面的每一个数字作比较，否则时间复杂度就是O（n2），因此我们可以考虑先比较两个相邻的数字。 如图5.1（a）和图5.1（b）所示，我们先把数组分解成两个长度为2的子数组，再把这两个子数组分别拆分成两个长度为1的子数组。接下来一边合并相邻的子数组，一边统计逆序对的数目。在第一对长度为1的子数组{7}、{5}中7大于5，因此（7,5）组成一个逆序对。同样在第二对长度为1的子数组{6}、{4}中也有逆序对（6,4）。由于我们已经统计了这两对子数组内部的逆序对，因此需要把这两对子数组排序（图5.1（c）所示），以免在以后的统计过程中再重复统计。  图5.1 统计数组{7,5,6,4}中逆序对的过程 注：图中省略了最后一步，即复制第二个子数组最后剩余的4到辅助数组中。（a）P1指向的数字大于P2指向的数字，表明数组中存在逆序对。P2指向的数字是第二个子数组的第二个数字，因此第二个子数组中有两个数字比7小。把逆序对数目加2，并把7复制到辅助数组，向前移动P1和P3。（b）P1指向的数字小于P2指向的数字，没有逆序对。把P2指向的数字复制到辅助数组，并向前移动P2和P3。（c）P1指向的数字大于P2指向的数字，因此存在逆序对。由于P2指向的数字是第二个子数组的第一个数字，子数组中只有一个数字比5小。把逆序对数目加1，并把5复制到辅助数组，向前移动P1和P3。 接下来我们统计两个长度为2的子数组之间的逆序对。我们在图5.2中细分图5.1（d）的合并子数组及统计逆序对的过程。  图5.2 图5.1（d）中合并两个子数组并统计逆序对的过程 我们先用两个指针分别指向两个子数组的末尾，并每次比较两个指针指向的数字。如果第一个子数组中的数字大于第二个子数组中的数字，则构成逆序对，并且逆序对的数目等于第二个子数组中剩余数字的个数（如图5.2（a）和图5.2（c）所示）。如果第一个数组中的数字小于或等于第二个数组中的数字，则不构成逆序对（如图5.2（b）所示）。每一次比较的时候，我们都把较大的数字从后往前复制到一个辅助数组中去，确保辅助数组中的数字是递增排序的。在把较大的数字复制到辅助数组之后，把对应的指针向前移动一位，接下来进行下一轮比较。 经过前面详细的讨论，我们可以总结出统计逆序对的过程：先把数组分隔成子数组，先统计出子数组内部的逆序对的数目，然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中，还需要对数组进行排序。如果对排序算法很熟悉，我们不难发现这个排序的过程实际上就是归并排序。我们可以基于归并排序写出如下代码：   我们知道归并排序的时间复杂度是O（nlogn），比最直观的O（n2）要快，但同时归并排序需要一个长度为n的辅助数组，相当于我们用O（n）的空间消耗换来了时间效率的提升，因此这是一种用空间换时间的算法。 源代码： 本题完整的源代码详见36\_InversePairs项目。 测试用例： ● 功能测试（输入未经排序的数组、递增排序的数组、递减排序的数组，输入的数组中包含重复的数字）。 ● 边界值测试（输入的数组中只有两个数字、数组的数组只有一个数字） ● 特殊输入测试（表示数组的指针为NULL指针）。 本题考点： ● 考查分析复杂问题的能力。统计逆序对的过程很复杂，如何发现逆序对的规律，是应聘者解决这个题目的关键。 ● 考查应聘者对归并排序的掌握程度。如果应聘者在分析统计逆序对的过程中发现问题与归并排序的相似性，并能基于归并排序形成解题思路，那通过这轮面试的几率就很高了。 面试题37：两个链表的第一个公共结点 题目：输入两个链表，找出它们的第一个公共结点。链表结点定义如下：  面试的时候碰到这道题，很多应聘者的第一反应就是蛮力法：在第一链表上顺序遍历每个结点，每遍历到一个结点的时候，在第二个链表上顺序遍历每个结点。如果在第二个链表上有一个结点和第一个链表上的结点一样，说明两个链表在这个结点上重合，于是就找到了它们的公共结点。如果第一个链表的长度为m，第二个链表的长度为n，显然该方法的时间复杂度是O（mn）。 通常蛮力法不会是最好的办法，我们接下来试着分析有公共结点的两个链表有哪些特点。从链表结点的定义可以看出，这两个链表是单向链表。如果两个单向链表有公共的结点，那么这两个链表从某一结点开始，它们的m\_pNext都指向同一个结点。但由于是单向链表的结点，每个结点只有一个m\_pNext，因此从第一个公共结点开始，之后它们所有结点都是重合的，不可能再出现分叉。所以两个有公共结点而部分重合的链表，拓扑形状看起来像一个Y，而不可能像X（如图5.3所示）。  图5.3 两个链表在值为6的结点处交汇 经过分析我们发现，如果两个链表有公共结点，那么公共结点出现在两个链表的尾部。如果我们从两个链表的尾部开始往前比较，最后一个相同的结点就是我们要找的结点。可问题是在单向链表中，我们只能从头结点开始按顺序遍历，最后才能到达尾结点。最后到达的尾结点却要最先被比较，这听起来是不是像“后进先出”？于是我们就能想到用栈的特点来解决这个问题：分别把两个链表的结点放入两个栈里，这样两个链表的尾结点就位于两个栈的栈顶，接下来比较两个栈顶的结点是否相同。如果相同，则把栈顶弹出接着比较下一个栈顶，直到找到最后一个相同的结点。 在上述思路中，我们需要用两个辅助栈。如果链表的长度分别为m和n，那么空间复杂度是O（m＋n）。这种思路的时间复杂度也是O（m＋n）。和最开始的蛮力法相比，时间效率得到了提高，相当于是用空间消耗换取了时间效率。 之所以需要用到栈，是因为我们想同时遍历到达两个栈的尾结点。当两个链表的长度不相同时，如果我们从头开始遍历到达尾结点的时间就不一致。其实解决这个问题还有一个更简单的办法：首先遍历两个链表得到它们的长度，就能知道哪个链表比较长，以及长的链表比短的链表多几个结点。在第二次遍历的时候，在较长的链表上先走若干步，接着再同时在两个链表上遍历，找到的第一个相同的结点就是它们的第一个公共结点。 比如在图5.3的两个链表中，我们可以先遍历一次得到它们的长度分别为5和4，也就是较长的链表与较短的链表相比多一个结点。第二次先在长的链表上走1步，到达结点2。接下来分别从结点2和结点4出发同时遍历两个结点，直到找到它们第一个相同的结点6，这就是我们想要的结果。 第三种思路和第二种思路相比，时间复杂度都是O（m＋n），但我们不再需要辅助的栈，因此提高了空间效率。当面试官首肯了我们最后一种思路之后，就可以动手写代码了。下面是一段参考代码：  源代码： 本题完整的源代码详见37\_FirstCommonNodesInLists项目。 测试用例： ● 功能测试（输入的两个链表有公共交点：第一个公共结点在链表的中间，第一个公共结点在链表的末尾，第一个公共结点是链表的头结点；输入的两个链表没有公共结点）。 ● 特殊输入测试（输入的链表头结点是NULL指针） 本题考点： ● 考查应聘者对时间复杂度和空间复杂度的理解及分析能力。解决这道题有多种不同的思路。每当应聘者想到一种思路的时候，都要很快分析出这种思路的时间复杂度和空间复杂度是多少，并找到可以优化的地方。 ● 考查应聘者对链表的编程能力。 相关题目： 如果把图5.3逆时针旋转90°，我们就会发现两个链表的拓扑形状和一棵树的形状非常相似，只是这里的指针是从叶结点指向根结点的。两个链表的第一个公共结点正好就是二叉树中两个叶节点的最低公共祖先。在本书7.2节，我们将详细讨论如何求两个结点的最低公共祖先。 5.4 本章小结 编程面试的时候，面试官通常对时间复杂度和空间复杂度都会有要求，并且一般情况下面试官更加关注时间复杂度。 降低时间复杂度的第一个方法是改用更加高效的算法。比如我们用动态规划解答面试题31“连续子数组的最大和”能够把时间复杂度降低到O（n），利用快速排序的Partition函数也能在O（n）时间解决面试题29“数组中出现次数超过一半的数字”和面试题30“最小的k个数字”。 降低时间复杂度的第二个方法是用空间换取时间。在解决面试题35“第一个只出现一次的字符”的时候，我们用数组实现一个简单的哈希表，于是用O（1）时间就能知道任意字符出现的次数。这种思路可以解决很多同类型的题目。另外，我们可以创建一个缓存保存中间的计算结果，从而避免重复的计算。面试题34“丑数”就是这方面的一个例子。在用递归的思路求解问题的时候，如果有重复的子问题，同样我们也可以通过保存求解子问题的结果来避免重复计算。更多关于递归的讨论请参考本书的2.4.2节及面试题9“斐波那契数列”。 值得注意的是，以空间换取时间并不一定都是可行的方案。我们要注意需要的辅助空间的大小，消耗太多的内存可能得不偿失。另外，我们还要关注问题的背景。如果面试题是有关嵌入式开发的，那对空间消耗就要格外留心，因为通常嵌入式系统的内存很有限。