5.2 时间效率

由于每个人都希望软件的响应时间尽量短一些，所以软件公司都很重视软件的时间性能，都会在发布软件之前花不少精力进行时间效率优化。这也就不难理解为什么很多公司的面试官都把代码的时间效率当作一个考查重点。面试官除了考查应聘者的编程能力，还关注应聘者有没有不断优化效率、追求完美的态度和能力。

首先，我们的编程习惯对代码的时间效率有很大影响。比如C/C++程序员要养成采用引用（或指针）传递复杂类型参数的习惯。如果采用值传递的方式，则从形参到实参会产生一次复制操作。这样的复制是多余的操作，我们应该尽量避免。再举个例子，如果用C#做多次字符串的拼接操作，则不要多次用String的+运算符来拼接字符串，因为这样会产生很多String的临时实例，造成时间和空间的浪费。更好的办法是用StringBuilder的Append方法来完成字符串的拼接。如果我们平时不太注意这些影响代码效率的细节，没有养成好的编码习惯，那么我们写出的代码可能会让面试官大失所望。

其次，即使同一个算法用循环和递归两种思路实现的时间效率可能会大不一样。递归的本质是把一个大的复杂问题分解成两个或者多个小的简单问题。如果小问题中有相互重叠的部分，那么直接用递归实现虽然代码显得很简洁，但时间效率可能会非常差（详细讨论见本书2.4.1节）。对于这种类型的题目，我们可以用递归的思路来分析问题，但写代码的时候可以用数组（一维或者多维数组）来保存中间结果基于循环实现。绝大部分动态规划算法的分析和代码实现都是分这两个步骤完成的。详细的讨论请参考面试题47“礼物的最大价值”和面试题48“最长不含重复字符的子字符串”。

再次，代码的时间效率还能体现应聘者对数据结构和算法功底的掌握程度。同样是查找，如果是顺序查找则需要O(n)的时间；如果输入的是排序的数组则只需要O(logn)的时间；如果事先已经构造好了哈希表，那么查找在O(1)时间内就能完成。我们只有对常见的数据结构和算法都了然于胸，才能在需要的时候选择合适的数据结构和算法来解决问题。

最后，应聘者在面试的时候要展示敏捷的思维能力和追求完美的激情。听到题目的时候，我们一般很快就能想到最直观的算法。这个最直观的办法很有可能不是最优的，但也不妨在第一时间告诉面试官，这样面试官至少会觉得我们思维比较敏捷。我们想到几种思路之后，面试官可能仍然不满意，还在提示我们有更好的办法。这时候我们一定不能轻言放弃，而要表现出积极思考的态度，努力从不同的角度去思考问题。有些题目很难，面试官甚至不期待应聘者在短短几十分钟里想出完美的解法，但他会希望应聘者能够有激情、有耐心地去尝试新的思路，而不是碰到难题就退缩。在面试的时候，应聘者的态度和激情对最终的面试结果也有很重要的影响。

面试题39：数组中出现次数超过一半的数字

题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如，输入一个长度为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，那么中位数应该位于它的右边，我们可以接着在它的右边部分的数组中查找。这是一个典型的递归过程，可以用如下代码实现：

int MoreThanHalfNum(int* numbers, int length)

{

if(CheckInvalidArray(numbers, length))

return 0;

int middle = length >> 1;

int start = 0;

int end = length - 1;

int index = Partition(numbers, length, start, end);

while(index != middle)

{

if(index > middle)

{

end = index - 1;

index = Partition(numbers, length, start, end);

}

else

{

start = index + 1;

index = Partition(numbers, length, start, end);

}

}

int result = numbers[middle];

if(!CheckMoreThanHalf(numbers, length, result))

result = 0;

return result;

}

上述代码中的函数Partition是完成快速排序的基础。我们在本书的2.4.2节详细讨论了这个函数，这里不再重复。

在面试的时候，除了要完成基本功能即找到符合要求的数字，还要考虑一些无效的输入。如果函数的输入参数是一个指针（数组在参数传递的时候退化为指针），就要考虑这个指针可能为nullptr。下面的函数CheckInvalidArray用来判断输入的数组是不是无效的。题目中说数组中有一个数字出现的次数超过数组长度的一半，如果输入的数组中出现频率最高的数字都没有达到这个标准，那该怎么办？这就是我们定义了一个CheckMoreThanHalf函数的原因。面试的时候我们要全面考虑这些情况，才能让面试官完全满意。下面的代码用一个全局变量来表示输入无效的情况。更多关于出错处理的讨论，详见本书3.3节。

bool g_bInputInvalid = false;

bool CheckInvalidArray(int* numbers, int length)

{

g_bInputInvalid = false;

if(numbers == nullptr || length <= 0)

g_bInputInvalid = true;

return g_bInputInvalid;

}

bool CheckMoreThanHalf(int* numbers, int length, int number)

{

int times = 0;

for(int i = 0; i < length; ++i)

{

if(numbers[i] == number)

times++;

}

bool isMoreThanHalf = true;

if(times * 2 <= length)

{

g_bInputInvalid = true;

isMoreThanHalf = false;

}

return isMoreThanHalf;

}

解法二：根据数组特点找出时间复杂度为O(n)的算法

接下来我们从另外一个角度来解决这个问题。数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现次数的和还要多。因此，我们可以考虑在遍历数组的时候保存两个值：一个是数组中的一个数字；另一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为零，那么我们需要保存下一个数字，并把次数设为1。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时对应的数字。

下面是这种思路的参考代码：

int MoreThanHalfNum(int* numbers, int length)

{

if(CheckInvalidArray(numbers, length))

return 0;

int result = numbers[0];

int times = 1;

for(int i = 1; i < length; ++i)

{

if(times == 0)

{

result = numbers[i];

times = 1;

}

else if(numbers[i] == result)

times++;

else

times--;

}

if(!CheckMoreThanHalf(numbers, length, result))

result = 0;

return result;

}

和第一种思路一样，我们也要检验输入的数组是不是有效的，这里不再重复。

解法比较

上述两种算法的时间复杂度都是O(n)。基于Partition函数的算法的时间复杂度的分析不是很直观，本书限于篇幅不作详细讨论，感兴趣的读者可以参考《算法导论》等书籍的相关章节。我们注意到，在第一种解法中，需要交换数组中数字的顺序，这就会修改输入的数组。是不是可以修改输入的数组呢？在面试的时候，我们可以和面试官讨论，让他明确需求。如果面试官说不能修改输入的数组，那就只能采用第二种解法了。

源代码：

本题完整的源代码：

https://github.com/zhedahht/CodingInterviewChinese2/tree/master/39_ MoreThanHalfNumber

测试用例：

功能测试（输入的数组中存在一个出现次数超过数组长度一半的数字；输入的数组中不存在一个出现次数超过数组长度一半的数字）。

特殊输入测试（输入的数组中只有一个数字；输入nullptr指针）。

本题考点：

考查应聘者对时间复杂度的理解。应聘者每想出一种解法，面试官都期待他能分析出这种解法的时间复杂度是多少。

考查应聘者思维的全面性。面试官除了要求应聘者能对有效的输入返回正确的结果，同时也期待应聘者能对无效的输入进行相应的处理。

面试题40：最小的k个数

题目：输入n个整数，找出其中最小的k个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

这道题最简单的思路莫过于把输入的n个整数排序，排序之后位于最前面的k个数就是最小的k个数。这种思路的时间复杂度是O(nlogn)，面试官会提示我们还有更快的算法。

解法一：时间复杂度为O(n)的算法，只有当我们可以修改输入的数组时可用

从解决面试题39“数组中出现次数超过一半的数字”得到了启发，我们同样可以基于Partition函数来解决这个问题。如果基于数组的第k个数字来调整，则使得比第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组的右边。这样调整之后，位于数组中左边的k个数字就是最小的k个数字（这k个数字不一定是排序的）。下面是基于这种思路的参考代码：

void GetLeastNumbers(int* input, int n, int* output, int k)

{

if(input == nullptr || output == nullptr || k > n || n <= 0 || k <= 0)

return;

int start = 0;

int end = n - 1;

int index = Partition(input, n, start, end);

while(index != k - 1)

{

if(index > k - 1)

{

end = index - 1;

index = Partition(input, n, start, end);

}

else

{

start = index + 1;

index = Partition(input, n, start, end);

}

}

for(int i = 0; i < k; ++i)

output[i] = input[i];

}

采用这种思路是有限制的。我们需要修改输入的数组，因为函数Partition会调整数组中数字的顺序。如果面试官要求不能修改输入的数组，那么我们该怎么办呢？

解法二：时间复杂度为O(nlogk)的算法，特别适合处理海量数据

我们可以先创建一个大小为k的数据容器来存储最小的k个数字，接下来每次从输入的n个整数中读入一个数。如果容器中已有的数字少于k个，则直接把这次读入的整数放入容器之中；如果容器中已有k个数字了，也就是容器已满，此时我们不能再插入新的数字而只能替换已有的数字。找出这已有的k个数中的最大值，然后拿这次待插入的整数和最大值进行比较。如果待插入的值比当前已有的最大值小，则用这个数替换当前已有的最大值；如果待插入的值比当前已有的最大值还要大，那么这个数不可能是最小的k个整数之一，于是我们可以抛弃这个整数。

因此，当容器满了之后，我们要做3件事情：一是在k个整数中找到最大数；二是有可能在这个容器中删除最大数；三是有可能要插入一个新的数字。如果用一棵二叉树来实现这个数据容器，那么我们能在O(logk)时间内实现这3步操作。因此，对于n个输入数字而言，总的时间效率就是O(nlogk)。

我们可以选择用不同的二叉树来实现这个数据容器。由于每次都需要找到k个整数中的最大数字，我们很容易想到用最大堆。在最大堆中，根节点的值总是大于它的子树中任意节点的值。于是我们每次可以在O(1)时间内得到已有的k个数字中的最大值，但需要O(logk)时间完成删除及插入操作。

我们自己从头实现一个最大堆需要一定的代码，这在面试短短的几十分钟内很难完成。我们还可以采用红黑树来实现我们的容器。红黑树通过把节点分为红、黑两种颜色并根据一些规则确保树在一定程度上是平衡的，从而保证在红黑树中的查找、删除和插入操作都只需要O(logk)时间。在STL中，set和multiset都是基于红黑树实现的。如果面试官不反对我们用STL中的数据容器，那么我们可以直接拿过来用。下面是基于STL中的multiset的参考代码：

typedef multiset<int, greater<int> > intSet;

typedef multiset<int, greater<int> >::iterator setIterator;

void GetLeastNumbers(const vector<int>& data, intSet& leastNumbers, int k)

{

leastNumbers.clear();

if(k < 1 || data.size() < k)

return;

vector<int>::const_iterator iter = data.begin();

for(; iter != data.end(); ++ iter)

{

if((leastNumbers.size()) < k)

leastNumbers.insert(*iter);

else

{

setIterator iterGreatest = leastNumbers.begin();

if(*iter < *(leastNumbers.begin()))

{

leastNumbers.erase(iterGreatest);

leastNumbers.insert(*iter);

}

}

}

}

解法比较

基于函数Partition的第一种解法的平均时间复杂度是O(n)，比第二种解法要快，但同时它也有明显的限制，比如会修改输入的数组。

第二种解法虽然慢一点，但它有两个明显的优点。一是没有修改输入的数据（代码中的变量data）。我们每次只是从data中读入数字，所有的写操作都是在容器leastNumbers中进行的。二是该算法适合海量数据的输入（包括百度在内的多家公司非常喜欢与海量输入数据相关的问题）。假设题目是要求从海量的数据中找出最小的k个数字，由于内存的大小是有限的，有可能不能把这些海量的数据一次性全部载入内存。这个时候，我们可以从辅助存储空间（如硬盘）中每次读入一个数字，根据GetLeastNumbers的方式判断是不是需要放入容器leastNumbers即可。这种思路只要求内存能够容纳leastNumbers即可，因此它最适合的情形就是n很大并且k较小的问题。

我们可以用表5.1总结这两种解法的特点。

表5.1 两种解法的特点比较

基于Partition函数的解法 基于堆或者红黑树的解法

时间复杂度 O(n) O(nlogk)

是否需要修改输入数组 是 否

是否适用于海量数据 否 是

由于这两种解法各有优缺点，各自适用于不同的场合，因此应聘者在动手做题之前要先问清楚题目的要求，包括输入的数据量有多大、能否一次性载入内存、是否允许交换输入数据中数字的顺序等。

面试小提示：

如果面试时遇到的面试题有多种解法，并且每种解法都各有优缺点，那么我们要向面试官问清楚题目的要求、输入的特点，从而选择最合适的解法。

源代码：

本题完整的源代码：

https://github.com/zhedahht/CodingInterviewChinese2/tree/master/40_ KLeastNumbers

测试用例：

功能测试（输入的数组中有相同的数字；输入的数组中没有相同的数字）。

边界值测试（输入的k等于1或者等于数组的长度）。

特殊输入测试（k小于1；k大于数组的长度；指向数组的指针为NULL）。

本题考点：

考查应聘者对时间复杂度的分析能力。面试的时候每想出一种解法，我们都要能分析出这种解法的时间复杂度是多少。

如果采用第一种思路，则本题考查应聘者对Partition函数的理解。这个函数既是快速排序的基础，也可以用来查找n个数中第k大的数字。

如果采用第二种思路，则本题考查应聘者对堆、红黑树等数据结构的理解。当需要在某个数据容器内频繁查找及替换最大值时，我们要想到二叉树是一个合适的选择，并能想到用堆或者红黑树等特殊的二叉树来实现。

面试题41：数据流中的中位数

题目：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

由于数据是从一个数据流中读出来的，因而数据的数目随着时间的变化而增加。如果用一个数据容器来保存从流中读出来的数据，则当有新的数据从流中读出来时，这些数据就插入数据容器。这个数据容器用什么数据结构定义最合适呢？

数组是最简单的数据容器。如果数组没有排序，则可以用Partition函数找出数组中的中位数（详见面试题39）。在没有排序的数组中插入一个数字和找出中位数的时间复杂度分别是O(1)和O(n)。

我们还可以在往数组里插入新数据时让数组保持排序。这时由于可能需要移动O(n)个数，因此需要O(n)时间才能完成插入操作。在已经排好序的数组中找出中位数是一个简单的操作，只需要O(1)时间即可完成。

排序的链表是另外一种选择。我们需要O(n)时间才能在链表中找到合适的位置插入新的数据。如果定义两个指针指向链表中间的节点（如果链表的节点数目是奇数，那么这两个指针指向同一个节点），那么可以在O(1)时间内得出中位数。此时的时间复杂度与基于排序的数组的时间复杂度一样。

二叉搜索树可以把插入新数据的平均时间降低到O(logn)。但是，当二叉搜索树极度不平衡从而看起来像一个排序的链表时，插入新数据的时间仍然是O(n)。为了得到中位数，可以在二叉树节点中添加一个表示子树节点数目的字段。有了这个字段，可以在平均O(logn)时间内得到中位数，但最差情况仍然需要O(n)时间。

为了避免二叉搜索树的最差情况，还可以利用平衡的二叉搜索树，即AVL树。通常AVL树的平衡因子是左、右子树的高度差。可以稍作修改，把AVL的平衡因子改为左、右子树节点数目之差。有了这个改动，可以用O(logn)时间往AVL树中添加一个新节点，同时用O(1)时间得到所有节点的中位数。

AVL树的时间效率很高，但大部分编程语言的函数库中都没有实现这个数据结构。应聘者在短短几十分钟内实现AVL树的插入操作是非常困难的，于是我们不得不再分析还有没有其他的方法。

如图5.1所示，如果数据在容器中已经排序，那么中位数可以由P1和P2指向的数得到。如果容器中数据的数目是奇数，那么P1和P2指向同一个数据。

图5.1 容器中数据被中间的一个或两个数据分隔成两部分：（a）数据的数目是奇数；（b）数据的数目是偶数

我们注意到整个数据容器被分隔成两部分。位于容器左边部分的数据比右边的数据小。另外，P1指向的数据是左边部分最大的数，P2指向的数据是左边部分最小的数。

如果能够保证数据容器左边的数据都小于右边的数据，那么即使左、右两边内部的数据没有排序，也可以根据左边最大的数及右边最小的数得到中位数。如何快速从一个数据容器中找出最大数？用最大堆实现这个数据容器，因为位于堆顶的就是最大的数据。同样，也可以快速从最小堆中找出最小数。

因此，可以用如下思路来解决这个问题：用一个最大堆实现左边的数据容器，用一个最小堆实现右边的数据容器。往堆中插入一个数据的时间效率是O(logn)。由于只需要O(1)时间就可以得到位于堆顶的数据，因此得到中位数的时间复杂度是O(1)。

表5.2总结了使用没有排序的数组、排序的数组、排序的链表、二叉搜索树、AVL数、最大堆和最小堆几种不同的数据结构的时间复杂度。

表5.2 使用没有排序的数组、排序的数组、排序的链表、二叉搜索树、AVL树、最大堆和最小堆等不同数据结构的时间复杂度

数据结构 插入的时间复杂度 得到中位数的时间复杂度

没有排序的数组 O(1) O(n)

排序的数组 O(n) O(1)

排序的链表 O(n) O(1)

续表

数据结构 插入的时间复杂度 得到中位数的时间复杂度

二叉搜索树 平均O(logn)，最差O(n) 平均O(logn)，最差O(n)

AVL数 O(logn) O(1)

最大堆和最小堆 O(logn) O(1)

接下来考虑用最大堆和最小堆实现的一些细节。首先要保证数据平均分配到两个堆中，因此两个堆中数据的数目之差不能超过1。为了实现平均分配，可以在数据的总数目是偶数时把新数据插入最小堆，否则插入最大堆。

还要保证最大堆中的所有数据都要小于最小堆中的数据。当数据的总数目是偶数时，按照前面的分配规则会把新的数据插入最小堆。如果此时这个新的数据比最大堆中的一些数据要小，那该怎么办呢？

可以先把这个新的数据插入最大堆，接着把最大堆中最大的数字拿出来插入最小堆。由于最终插入最小堆的数字是原最大堆中最大的数字，这样就保证了最小堆中所有数字都大于最大堆中的数字。

当需要把一个数据插入最大堆，但这个数据小于最小堆里的一些数据时，这个情形和前面类似，请大家自己分析。

以下是用C++实现的参考代码。我们基于STL中的函数push_heap、pop_heap及vector实现堆。比较仿函数less和greater分别用来实现最大堆和最小堆。

template<typename T> class DynamicArray

{

public:

void Insert(T num)

{

if(((min.size() + max.size()) & 1) == 0)

{

if(max.size() > 0 && num < max[0])

{

max.push_back(num);

push_heap(max.begin(), max.end(), less<T>());

num = max[0];

pop_heap(max.begin(), max.end(), less<T>());

max.pop_back();

}

min.push_back(num);

push_heap(min.begin(), min.end(), greater<T>());

}

else

{

if(min.size() > 0 && min[0] < num)

{

min.push_back(num);

push_heap(min.begin(), min.end(), greater<T>());

num = min[0];

pop_heap(min.begin(), min.end(), greater<T>());

min.pop_back();

}

max.push_back(num);

push_heap(max.begin(), max.end(), less<T>());

}

}

T GetMedian()

{

int size = min.size() + max.size();

if(size == 0)

throw exception("No numbers are available");

T median = 0;

if((size & 1) == 1)

median = min[0];

else

median = (min[0] + max[0]) / 2;

return median;

}

private:

vector<T> min;

vector<T> max;

};

在上述代码中，min是一个最小堆，max是一个最大堆。函数Insert用来插入从数据流中读出来的数据，函数GetMedian用来得到已有所有数据的中位数。

源代码：

本题完整的源代码：

https://github.com/zhedahht/CodingInterviewChinese2/tree/master/41_ StreamMedian

测试用例：

功能测试（从数据流中读出奇数个数字；从数据流中读出偶数个数字）。

边界值测试（从数据流中读出0个、1个、2个数字）

本题考点：

考查应聘者对时间复杂度的分析能力。

考查应聘者对数据结构的理解程度。应聘者只有对各个常用数据容器的特点非常了解，知道它们的优缺点及适用场景，才能找出最优的解法。

面试题42：连续子数组的最大和

题目：输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为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本身还小。也就是说，从第一个数字开始的子数