3.4 达人修炼真题

1.如何在不排序的情况下求数组中的中位数

题目描述：

所谓中位数就是一组数据从小到大排列后中间的那个数字。如果数组长度为偶数，那么中位数的值就是中间两个数字相加除以2，如果数组长度为奇数，那么中位数的值就是中间那个数字。

分析与解答：

根据定义，如果数组是一个已经排序好的数组，那么直接通过索引即可获得所需的中位数。如果题目允许排序的话，那么本题的关键在于选取一个合适的排序算法对数组进行排序。一般而言，快速排序的平均时间复杂度较低，为O(nlog₂n)，所以，如果采用排序方法的话，算法的平均时间复杂度为O(nlog₂n)。

但题目要求不许使用排序算法。此时，可以换一种思维：分治的思想。快速排序算法在每一次局部递归后都保证某个元素左侧元素的值都比它小，右侧元素的值都比它大，因此，可以利用这个思路快速地找到第n大元素，而与快速排序算法不同的是，这个算法关注的并不是元素的左右两边，而仅仅是某一边。

可以采用一种类似快速排序的方法，找出这个中位数来。具体而言，首先把问题转化为求一列数中第i小的数的问题，求中位数就是求一列数的第（length/2+1）小的数的问题（其中length表示的是数组序列的长度）。

当使用一次类快速排序算法后，分割元素的下标为pos：

1）当pos>length/2时，说明中位数在数组左半部分，那么继续在左半部分查找。

2）当pos==length/2时，说明找到该中位数，返回A[pos]即可。

3）当pos<length/2时，说明中位数在数组右半部分，那么继续在数组右半部分查找。

以上默认此数组序列长度为奇数，如果为偶数就调用上述方法两次找到中间的两个数求平均。示例代码如下：

程序的运行结果为

算法性能分析：

这个算法在平均情况下的时间复杂度为O(n)。

2.如何从大量的url中找出相同的url

题目描述：

给定a、b两个文件，各存放50亿个url，每个url各占64B，内存限制是4GB，请找出a、b两个文件共同的url。

分析解答：

由于每个url需要占64B，所以50亿个url占用的空间大小为50亿×64=5G×64=320GB。由于内存大小只有4GB，因此不可能一次性把所有的url都加载到内存中处理。对于这个类型的题目，一般都需要使用分治法，即把一个文件中的url按照某一特征分成多个文件，使得每个文件的内容都小于4GB，这样就可以把这个文件一次性读到内存中进行处理了。对于本题而言，主要的实现思路如下：

1）遍历文件a，对遍历到的url求hash(url)%500，根据计算结果把遍历到的url分别存储到a₀,a₁,a₂,…,a₄₉₉（计算结果为i的url存储到文件a_i中），这样每个文件的大小大约为600MB。当某一个文件中url的大小超过2GB的时候，可以按照类似的思路把这个文件继续分为更小的子文件（例如：如果a1大小超过2GB，那么可以把文件继续分成a₁₁,a₁₂……）。

2）使用同样的方法遍历文件b，把文件b中的url分别存储到文件b₀,b₁,…,b₄₉₉中。

3）通过上面的划分，与a_i中url相同的url一定在b_i中。由于a_i与b_i中所有的url的大小不会超过4GB，因此可以把它们同时读入到内存中进行处理。具体思路是：遍历文件a_i，把遍历到的url存入到hash_set中，接着遍历文件b_i中的url，如果这个url在hash_set中存在，那么说明这个url是这两个文件共同的url，可以把这个url保存到另外一个单独的文件中。当把文件a₀～a₄₉₉都遍历完成后，就找到了两个文件共同的url。

3.如何实现链表的逆序

题目描述：

给定一个带头结点的单链表，请将其逆序。即如果单链表原来为head->1->2->3->4->5->6->7，则逆序后变为head->7->6->5->4->3->2->1。

分析与解答：

由于单链表与数组不同，单链表中每个结点的地址都存储在其前驱结点的指针域中，因此对单链表中任何一个结点的访问只能从链表的头指针开始进行遍历。在对链表的操作过程中，需要特别注意在修改结点指针域的时候，记录下后继结点的地址，否则就会丢失后继结点。

方法一：就地逆序

主要思路：在遍历链表的时候，修改当前结点的指针域的指向，让其指向它的前驱结点。为此需要用一个指针变量来保存前驱结点的地址。此外，为了在调整当前结点指针域的指向后还能找到后继结点，还需要另外一个指针变量来保存后继结点的地址，在所有结点都被保存好以后就可以直接完成指针的逆序了。除此之外，还需要特别注意对链表首尾结点的特殊处理。具体实现方式如图3-2所示。

在上图中，假设当前已经遍历到cur结点，由于它所有的前驱结点都已经完成了逆序操作，因此只需要使cur->next=pre即可完成逆序操作，在此之前为了能够记录当前结点的后继结点的地址，需要用一个额外的指针next来保存后继结点的信息，通过上图（1）～（4）四步把实线的指针调整为虚线的指针就可以完成当前结点的逆序；当前结点完成逆序后，可以通过向后移动指针来对后续的结点用同样的方法进行逆序操作。算法实现如下：

首先给出单链表数据结构的定义示例：

基于这个链表结构，逆序的实现方式如下：

程序的运行结果为

算法性能分析：

以上这种方法只需要对链表进行一次遍历，因此时间复杂度为O(n)，其中n为链表的长度。但是需要常数个额外的变量来保存当前结点的前驱结点与后继结点，因此空间复杂度为O(1)。

方法二：递归法

假定原链表为1->2->3->4->5->6->7，递归法的主要思路为：先逆序除第一个结点以外的子链表（将1->2->3->4->5->6->7变为1->7->6->5->4->3->2），接着把结点1添加到逆序的子链表的后面（1->2->3->4->5->6->7变为7->6->5->4->3->2->1）。同理，在逆序链表2->3->4->5->6->7时，也是先逆序子链表3->4->5->6->7（逆序为2->7->6->5->4->3），接着实现链表的整体逆序（2->7->6->5->4->3转换为7->6->5->4->3->2）。实现代码如下：

把方法一的main部分中Reverse(head)改成Reverse(&head)运行该方法可以得到相同的运行结果。

算法性能分析：

由于递归法也只需要对链表进行一次遍历，因此算法的时间复杂度也为O(n)，其中n为链表的长度。递归法的主要优点是：思路清晰，容易理解，而且也不需要保存前驱结点的地址；缺点是：算法实现的难度较大，此外，由于递归法需要不断地调用自己，需要额外的压栈与弹栈操作，因此与方法一相比，性能会有所下降。

方法三：插入法

插入法的主要思路为：从链表的第二个结点开始，把遍历到的结点插入到头结点的后面，直到遍历结束。假定原链表为head->1->2->3->4->5->6->7，在遍历到2的时候，将其插入到头结点后，链表变为head->2->1->3->4->5->6->7。同理将后序遍历到的所有结点都插入到头结点head后，就可以实现链表的逆序。实现代码如下：

算法性能分析：

以上这种方法也只需要对单链表进行一次遍历，因此时间复杂度为O(n)，其中n为链表的长度。与方法一相比，这种方法不需要保存前驱结点的地址；与方法二相比，这种方法不需要递归的调用，效率更高。

引申：

1）对不带头结点的单链表进行逆序。

2）从尾到头输出链表。

分析与解答：

对不带头结点的单链表的逆序，读者可以自己练习（方法二已经实现了递归的方法），这里主要介绍单链表逆向输出的方法。

方法一：就地逆序+顺序输出

首先对链表进行逆序，然后顺序输出逆序后的链表。这个方法的缺点是改变了链表原来的结构。

方法二：逆序+顺序输出

先申请新的存储空间，对链表进行逆序，然后顺序输出逆序后的链表。逆序的主要思路为：每当遍历到一个结点的时候，就申请一块新的存储空间来存储这个结点的数据域，同时把新结点插入到新的链表的头结点后。这种方法的缺点是需要申请额外的存储空间。

方法三：递归输出

递归输出的主要思路为：先输出除当前结点外的后继子链表，然后输出当前结点。假如链表为：1->2->3->4->5->6->7，那么就先输出2->3->4->5->6->7，再输出1。同理，对于链表2->3->4->5->6->7，也是先输出3->4->5->6->7，接着输出2，直到遍历到链表的最后一个结点7的时候会输出结点7，然后递归地输出6，5，4，3，2，1。实现代码如下：

程序的运行结果为

算法性能分析：

以上这种方法只需要对链表进行一次遍历，因此时间复杂度为O(n)，其中n为链表的长度。

4.如何从无序链表中移除重复项

题目描述：

给定一个没有排序的链表，去掉其重复项，并保留原顺序，例如链表1->3->1->5->5->7，去掉重复项后变为1->3->5->7。

分析与解答：

方法一：顺序删除

主要思路：通过双重循环直接在链表上进行删除操作。外层循环用一个指针从第一个结点开始遍历整个链表，然后内层循环用另外一个指针遍历其余结点，将与外层循环遍历到的指针所指结点的数据域相同的结点删除。如图3-3所示：

假设外层循环从outerCur开始遍历，当内层循环指针innerCur遍历到上图实线所示的位置（outerCur->data==innerCur->data）时，需要把innerCur指向的结点删除。具体步骤如下：

1）用tmp记录待删除的结点的地址。

2）为了能够在删除tmp结点后继续遍历链表中其余的结点，使innerCur指向它的后继结点：innerCur=innerCur->next。

3）从链表中删除tmp结点。

4）释放tmp结点所占的内存空间。

实现代码如下：

程序的运行结果为

算法性能分析：

由于这个算法采用双重循环对链表进行遍历，因此时间复杂度为O(n²)，其中n为链表的长度。在遍历链表的过程中，使用了常量个额外的指针变量来保存当前遍历的结点、前驱结点和被删除的结点，因此空间复杂度为O(1)。

方法二：递归法

该方法的主要思路为：对于结点cur，首先递归地删除以cur->next为首的子链表中重复的结点，接着从以cur->next为首的子链表中找出与cur有着相同数据域的结点并删除。实现代码如下：

用方法一中的main函数运行这个方法可以得到相同的运行结果。

算法性能分析：

这个方法与方法一类似，从本质上而言，由于这个方法需要对链表进行双重遍历，因此时间复杂度为O(n²)，其中n为链表的长度。由于递归法会增加许多额外的函数调用，因此从理论上讲该方法的效率比方法一低。

方法三：空间换时间

通常情况下，为了降低时间复杂度，往往在条件允许的情况下，通过使用辅助空间实现。具体而言，主要思路如下：

1）建立一个hash_set，hash_set用来存储已经遍历过的结点，并将其初始化为空。

2）从头开始遍历链表中的所有结点，存在以下两种可能性：

① 如果结点内容已经在hash_set中，则删除此结点，继续向后遍历。

② 如果结点内容不在hash_set中，则保留此结点，并将此结点内容添加到hash_set中，继续向后遍历。

由于C语言类库中没有hash_set这个数据结构，如果要用C语言实现这种方式，那么只能自己实现hash_set。但是如果用C++语言实现，就非常简单了，因为C++语言的类库提供了hash_set。

引申：如何从有序链表中移除重复项

分析与解答：

上述介绍的方法也适用于链表有序的情况，但是由于以上方法没有充分利用链表有序这个条件，因此算法的性能肯定不是最优的。本题中，由于链表具有有序性，因此不需要对链表进行两次遍历。所以有如下思路：用cur指向链表第一个结点，此时需要分为以下两种情况讨论：

1）如果cur->data==cur->next->data，那么删除cur->next结点。

2）如果cur->data!=cur->next->data，那么cur=cur->next，继续遍历其余结点。

示例代码如下所示：

5.如何求一个字符串的所有排列

题目描述：

实现一个函数，当输入一个字符串时，要求输出这个字符串的所有排列。例如输入字符串abc，要求输出由字符a、b、c所能排列出来的所有字符串：abc,acb,bac,bca,cab,cba。

分析与解答：

这道题主要考察对递归的理解，可以采用递归的方法来实现。当然也可以使用非递归的方法来实现，但是与递归法相比，非递归法难度增加了很多。下面分别介绍这两种方法。

方法一：递归法

以下以字符串abc为例介绍对字符串进行全排列的方法。具体步骤如下所示：

1）首先固定第一个字符a，然后对后面的两个字符b与c进行全排列。

2）交换第一个字符与其后面的字符，即交换a与b，然后固定第一个字符b，接着对后面的两个字符a与c进行全排列。

3）由于第2）步交换了a和b，破坏了字符串原来的顺序，因此，需要再次交换a和b，使其恢复到原来的顺序，然后交换第一个字符与第三个字符（即交换a和c），接着固定第一个字符c，对后面的两个字符a与b求全排列。

在对字符串求全排列的时候就可以采用递归的方式来求解，实现方法如图3-4所示。

在使用递归方法求解的时候，需要注意以下两个问题：1）逐渐缩小问题的规模，并且可以用同样的方法来求解子问题。2）递归一定要有结束条件，否则会导致程序陷入死循环。本题目递归方法实现代码如下所示：

程序的运行结果为

算法性能分析：

假设这个算法需要的基本操作数为f(n)，那么f(n)=n*f(n-1)=n*(n-1)*f(n-2)…=n!。所以，算法的时间复杂度为O(n!)。算法在对字符进行交换的时候用到了常量个指针变量，因此，算法的空间复杂度为O(1)。

方法二：非递归法

递归法比较符合人的思维，因此，算法的思路以及算法实现都比较容易。下面介绍一种非递归的方法。算法的主要思想是：从当前字符串出发找出下一个排列（下一个排列为大于当前字符串的最小字符串）。

通过引入一个例子来介绍非递归算法的基本思想：假设要对字符串“12345”进行排序。第一个排列一定是“12345”，依此获取下一个排列：“12345”->“12354”->“12435”->“12453”->“12534”->“12543”->“13245”->…。从“12543”->“13245”可以看出找下一个排列的主要思路是：1）从右到左找到两个相邻递增（从左向右看是递增的）的字符，例如“12543”，从右到左找出第一个相邻递增的子串为“25”；将这个小的字符记为pmin。2）找出pmin后面的比它大的最小的字符进行交换，在本例中‘2’后面的子串中比它大的最小的字符为‘3’，因此，交换‘2’和‘3’得到字符串“13542”。3）为了保证下一个排列为大于当前字符串的最小字符串，在第2）步中完成交换后需要对pmin后的子串重新组合，使其值最小，只需对pmin后面的字符进行逆序即可（因为此时pmin后面的子字符串中的字符必定是按照降序排列，逆序后字符就按照升序排列了），逆序后就能保证当前的组合是新的最小的字符串；在这个例子中，上一步得到的字符串为“13542”，pmin指向字符‘3’，对其后面的子串“542”逆序后得到字符串“13245”。4）当找不到相邻递增的子串时，说明找到了所有的组合。

需要注意的是，这种方法适用于字符串中的字符是按照升序排列的情况。因此，非递归方法的主要思路为：1）首先对字符串进行排序（按字符进行升序排列）。2）依次获取当前字符串的下一个组合，直到找不到相邻递增的子串为止。实现代码如下：

程序的运行结果为

算法性能分析：

首先对字符串进行排序，时间复杂度为O(n²)，接着求字符串的全排列，由于长度为n的字符串全排列个数为n!，因此，Permutation函数中的循环执行的次数为n!，循环内部调用函数getNextPermutation，getNextPermutation内部用到了双重循环，因此，它的时间复杂度为O(n²)。所以，求全排列算法的时间复杂度为O(n!*n²)。

引申：如何去掉重复的排列

分析与解答：

当字符串中没有重复字符时，其所有组合对应的字符串也就没有重复的情况，但是当字符串中有重复字符时，例如“baa”，此时如果按照上面介绍的算法求全排列，就会有重复的字符串。

由于全排列的主要思路是从第一个字符起每个字符分别与它后面的字符进行交换，例如：对于“baa”，交换第一个与第二个字符后得到“aba”，再考虑交换第一个与第三个字符后得到“aab”，由于第二个字符与第三个字符相等，因此，会导致这两种交换方式对应的全排列是重复的（在固定第一个字符的情况下，它们对应的全排列都为“aab”和“aba”）。从上面的分析可以看出去掉重复排列的主要思路是：从第一个字符起每个字符分别与它后面非重复出现的字符进行交换。在递归方法的基础上只需要增加一个判断字符是否重复的函数即可，实现代码如下：

程序的运行结果为

6.如何计算一个数的n次方

题目描述：

给定一个数d和n，如何计算d的n次方？例如：d=2，n=3，d的n次方为2³=8。

分析与解答：

方法一：蛮力法

可以把n的取值分为如下几种情况：

1）n=0，那么计算结果肯定为1。

2）n=1，那么计算结果肯定为d。

3）n>0，计算方法是：初始化计算结果result=1，然后对result执行n次乘以d的操作，得到的结果就是d的n次方。

4）n<0，计算方法是：初始化计算结果result=1，然后对result执行|n|次除以d的操作，得到的结果就是d的n次方。

以2的3次方为例，首先初始化result=1，接着对result执行三次乘以2的操作：result=result*2=1*2=2，result=result*2=2*2=4，result=result*2=4*2=8，因此，2的3次方等于8。根据这个思路给出实现代码如下：

程序的运行结果为

算法性能分析：

这个算法的时间复杂度为O(n)，需要注意的是，当n非常大的时候，这种算法的效率是非常低的。

方法二：递归法

由于方法一没有充分利用中间的计算结果，因此，算法效率有很大的提升余地。例如在计算2的100次方时，假如已经计算出了2的50次方的值tmp，就没必要对tmp再乘以50次2了，可以直接利用tmp*tmp，就得到了结果。利用这个特点给出递归实现方法如下：

1）n=0，那么计算结果肯定为1。

2）n=1，那么计算结果肯定为d。

3）n>0，首先计算的值tmp，如果n为奇数，那么计算结果result=tmp*tmp*d，如果n为偶数，那么计算结果result=tmp*tmp。

4）n<0，首先计算的值tmp，如果n为奇数，那么计算结果result=1/(tmp*tmp*d)，如果n为偶数，那么计算结果result=1/(tmp*tmp)。

根据以上思路实现代码如下：

算法性能分析：

这个算法的时间复杂度为。

7.如何判断字符串是否为整数

题目描述：

写一个函数，检查字符串是否为整数，如果是，那么返回其整数值。

分析与解答：

整数分为负数、零与正数，负数只有一种表示方法，而正数可以有两种表示方法。例如：-123，123，+123。因此，在判断字符串是否为整数的时候，需要把这几种问题都考虑到。下面主要介绍两种方法。

方法一：递归法

对于正数而言，例如123，可以看成12×10+3，而12又可以看成1×10+2。而-123可以看成(-12)×10-3，-12可以被看成(-1)×10-2。根据这个特点可以采用递归的方法来求解，首先根据字符串的第一个字符确定整数的正负，接着对字符串从右往左遍历，假设字符串为“c₁c₂c₃…c_n”，如果c_n不是整数，那么这个字符串不能表示成整数；如果这个数是非负数(c₁=‘-’)，那么这个整数的值为“c₁c₂c₃…c_n-1”对应的整数值乘以10加上c_n对应的整数值，如果这个数是负数(c₁=‘-’)，那么这个整数的值为“c₁c₂c₃…c_n-1”对应的整数值乘以10减去c_n对应的整数值。而求解子字符串“c₁c₂c₃…c_n-1”对应的整数的时候，可以用相同的方法来求解，即采用递归的方法来求解。对于“+123”这种情况，首先去掉“+”，然后处理方法与“123”相同。由此可以得到递归表达式为

c₁=='-' ? toint(“c₁c₂c₃…c_n-1”)*10-(c_n-'0'):toint(“c₁c₂c₃…c_n-1”)*10+(c_n-'0')。

递归的结束条件是：当字符串长度为1时，直接返回字符对应的整数的值。实现代码如下：

程序的运行结果为

算法性能分析：

由于这个算法对字符串进行了一次遍历，因此，时间复杂度为O(n)，其中，n是字符串的长度。

方法二：非递归法

首先通过第一个字符的值确定整数的正负，然后去掉符号位，把后面的字符串当作正数来处理，处理完成后再根据整数的正负返回正确的结果。实现方法为从左到右遍历字符串计算整数的值，以“123”为例，遍历到‘1’的时候结果为1，遍历到‘2’的时候结果为1×10+2=12，遍历到‘3’的时候结果为12×10+3=123。其本质思路与方法一类似，根据这个思路实现代码如下：

算法性能分析：

由于这个算法对字符串进行了一次遍历，因此，算法的时间复杂度为O(n)，其中，n是指字符串的长度。但是由于方法一采用了递归法，而递归法需要大量的函数调用，也就有大量的压栈与弹栈操作（函数调用都是通过压栈与弹栈操作来完成的）。因此，虽然这两个方法有相同的时间复杂度，但是方法二的运行速度会比方法一更快，效率更高。

8.如何统计字符串中连续重复的字符个数

题目描述：

用递归的方式实现一个求字符串中连续出现相同字符的最大值，例如字符串“aaabbcc”中连续出现字符‘a’的最大值为3，字符串“abbc”中连续出现字符‘b’的最大值为2。

分析与解答：

如果不要求采用递归的方法，那么算法的实现就非常简单，只需要在遍历字符串的时候定义两个额外的变量curMaxLen与maxLen，分别记录与当前遍历的字符重复的连续字符的个数和遍历到目前为止找到的最长的连续重复字符的个数。在遍历的时候，如果相邻的字符相等，则执行curMaxLen+1；否则，更新最长连续重复字符的个数，即maxLen=max(curMaxLen, maxLen)，由于碰到了新的字符，因此，curMaxLen=1。

题目要求用递归的方法来实现，通过对非递归方法进行分析可知，在遍历字符串的时候，curMaxLen与maxLen是最重要的两个变量，那么在进行递归调用的时候，通过传入两个额外的参数（curMaxLen与maxLen）就可以采用与非递归方法类似的方法来实现，实现代码如下：

程序的运行结果为

算法性能分析：

由于这个算法对字符串进行了一次遍历，因此，算法的时间复杂度为O(n)。这个算法也没有申请额外的存储空间。

9.如何查找数组中元素的最大值和最小值

题目描述：

给定数组a1, a2, a3, ... an，要求找出数组中的最大值和最小值。假设数组中的值两两各不相同。

分析与解答：

虽然题目没有时间复杂度与空间复杂度的要求，但是给出的算法的时间复杂度肯定是越低越好。

方法一：蛮力法

查找数组中元素的最大值与最小值并不困难，最容易想到的方法就是蛮力法。具体过程如下：首先定义两个变量max与min，分别记录数组中最大值与最小值，并将其都初始化为数组的首元素的值，然后从数组的第二个元素开始遍历数组元素，如果遇到的数组元素的值比max大，那么该数组元素的值为当前的最大值，并将该值赋给max，如果遇到的数组元素的值比min小，那么该数组元素的值为当前的最小值，并将该值赋给min。

以数组{8,6,5,2,3,9,4,1,7}为例，示例代码如下所示：

程序的运行结果为

算法性能分析：

上述方法的时间复杂度为O(n)，但很显然，以上这个方法称不上是最优算法，因为最差情况下比较的次数达到了2n-2次（数组第一个元素首先赋值给max与min，接下来的n-1个元素都需要分别跟max与min比较一次，比较次数为2n-2），最好的情况下比较次数为n-1。是否可以降低比较次数呢？回答是肯定的，分治法就是一种高效的方法。

方法二：分治法

本题中，当采用分治法求解时，就是将数组两两一对分组，如果数组元素个数为奇数个，就把最后一个元素单独分为一组，然后分别对每组中的两个元素进行比较，把二者中值小的数放在数组的左边，值大的数放在数组右边，只需要比较n/2次就可以将数组分组完成。然后可以得出结论：最小值一定在每一组的左半部分，最大值一定在每一组的右半部分，接着只需要在每一组的左半部分找最小值，右半部分找最大值，查找分别需要比较n/2-1次和n/2-1次；因此，总共比较的次数大约为n/2*3=3n/2-2次。

实现代码如下：

程序的运行结果为

方法三：变形分治法

除了分治法以外，还有一种变形分治法，其具体步骤如下：将数组分成左右两部分，先求出左半部分的最大值和最小值，再求出右半部分的最大值和最小值，然后再综合比较，左右两部分的最大值中的较大值即为合并后的数组的最大值，左右两部分的最小值中的较小值即为合并后数组的最小值，通过此种方法即可求合并后的数组的最大值与最小值。

以上过程是个递归过程，对于划分后的左右两部分，同样重复这个过程，直到划分区间内只剩一个元素或者两个元素为止。

示例代码如下所示：

算法性能分析：

这个方法与方法二的思路从本质上讲是相同的，只不过这个方法是使用递归的方式实现的，因此，比较次数为3n/2-2。