第7章数组

第7章 数组

数组是由某种类型的数据按照一定的顺序组成的数据的集合。如果将有限个类型相同的变量的集合命名，那么这个名称为数组名。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。

数组是最基本的数据结构，关于数组的面试、笔试题在企业的招聘中也是屡见不鲜，求解此类题目，不仅需要扎实的编程基础，更需要清晰的思路与方法。本章列出的众多数组相关面试、笔试题，都非常具有代表性，需要读者重点关注。

7.1 如何找出数组中唯一的重复元素

难度系数：★★★☆☆

被考查系数：★★★★☆

题目描述：

数字1～1000放在含有1001个元素的数组中，其中只有唯一的一个元素值重复，其他数字均只出现一次。设计一个算法，将数组中重复元素找出来，要求每个数组元素只能访问一次。如果不使用辅助存储空间，能否设计一个算法实现？

分析与解答：

拿到题目，首先需要做的就是分析题目所要达到的目标及其中的限定条件。从题目的描述可以发现，本题的目标就是在一个有且仅有一个元素值重复的数组中找出这个唯一的重复元素，而限定条件就是每个数组元素只能访问一次，并且不许使用辅助存储空间。

方法一：空间换时间法

申请一个额外的数组用来存储每个数出现的次数，并把数组中所有元素初始化为0（假设数组为newArr，那么newArr[i]用来存储数字i+1出现的次数），显然重复元素就是出现次数大于0的元素。实现代码如下：

程序的运行结果为

算法性能分析：

上述方法是一种典型的以空间换时间的方法，它的时间复杂度为O（n），空间复杂度为O（n）。很显然，在题目没有明确限制的情况下，上述方法不失为一种好方法，但是由于题目要求不能用额外的辅助空间，所以上述方法不可取，是否存在其他满足题意的方法呢？

方法二：累加求和法

计算机技术与数学本身是一家，抛开计算机专业知识，上述问题其实可以转换成一个数学问题。数学问题的目标是在一个数字序列中寻找重复的那个数。根据题目意思可以看出，1～1000个数中，除了唯一一个数重复以外，其他各数有且仅有出现一次，由数学性质可知，这1001个数包括1～1000中的每一个数各1次，外加1～1000中某一个数。很显然，1001个数中有1000个数是固定的，唯一一个不固定的数也知道其范围（1～1000中某一个数），那么最容易想到的方法就是累加求和法。

所谓累加求和法，指的是将数组中的所有N+1（此处N的值取1000）个元素相加，然后用得到的和减去1+2+3+…+N（此处N的值为1000）的和，得到的差即为重复的元素的值。这一点不难证明。

由于1001个数的数据量较大，不方便说明以上算法。为了简化问题，以数组序列[1, 3, 4, 2, 5, 3]为例。该数组长度为6，除了数字3以外，其他4个数字没有重复。按照上述方法，首先计算数组中所有元素的和sumb，sumb=1+3+4+2+5+3=18，数组中只包含1～5的数，计算1～5一共5个数字的和suma，suma=1+2+3+4+5=15；所以，重复的数字的值为sumb-suma=3。由于本方法的代码实现较为简单，此处就不提供代码，有兴趣的读者可以自己实现。

算法性能分析：

上述方法的时间复杂度为O（n），空间复杂度为O（1）。

在使用求和法计算时，需要注意一个问题，即当数据量巨大时，有可能会导致计算结果溢出。以本题为例，1～1000范围内的1000个数累加，其和为（1+1000） ×1000/2，即500500，普通的int型变量能够表示出来，所以，本题中不存在此问题。但如果累加的数值巨大时，就很有可能溢出了。

此处是否还可以继续发散一下，如果累加求和法能够成立，累乘求积法是不是也是可以成立呢？只是累加求积法在使用的过程中很有可能会存在数据越界的情况，如果再由此定义一个大数乘法来，那就有点得不偿失了。所以，求积的方式是理论上成立的，只是在实际的使用过程中可操作性不强而已，一般更加推荐累加求和法。

方法三：异或法

采用以上累加求和的方法，虽然能够解决本题的问题，但也存在一个潜在的风险，就是当数组中的元素值太大或者数组太长时，计算的和有可能会出现溢出的情况，进而无法求解出数组中的唯一重复元素。

鉴于求和法存在的局限性，可以采用位运算中异或的方法。根据异或运算的性质可知，当相同元素异或时，其运算结果为0；当相异元素异或时，其运算结果为非0；任何数与数字0进行异或运算，其运算结果为该数。本题中，正好可以使用到此方法，即将数组里的元素逐一进行异或运算，得到的值再与数字1、2、3、…、N进行异或运算，得到的最终结果即为所求的重复元素。

以数组[1, 3, 4, 2, 5, 3]为例：

（1^3^4^2^5^3）^（1^2^3^4^5）=（1^1）^（2^2）^（3^3^3）^（4^4）^（5^5）=0^0^3^0^0=3。

实现代码如下：

程序的运行结果为

算法性能分析：

上述方法的时间复杂度为O（n），并且没有申请辅助的存储空间。

方法四：数据映射法

数组取值操作可以看作一个特殊的函数f:D→R，定义域为下标值0～1000，值域为1～1000。如果对任意一个数i，把f（i）叫作它的后继，i叫作f（i）的前驱。0只有后继，没有前驱，其他数字既有后继也有前驱，重复的那个数字有两个前驱。

采用此种方法，可以发现一个规律，即从0开始画一个箭头指向它的后继，从它的后继继续指向后继的后继，这样，必然会有一个结点指向之前已经出现过的数，即为重复的数。

利用下标与单元中所存储的内容之间的特殊关系进行遍历，一旦访问过该单元就赋予它一个标记（把数组中的元素变为它的相反数），再利用标记作为发现重复数字的关键。

以数组array=[1, 3, 4, 3, 5, 2 ]为例。从下标0开始遍历数组：

1）array[0]的值为1，说明没有被遍历过，接下来遍历下标为1的元素，同时标记已遍历过的元素（变为相反数）：array=[-1, 3, 4, 3, 5, 2 ];

2）array[1]的值为3，说明没被遍历过，接下来遍历下标为3的元素，同时标记已遍历过的元素：array=[-1,-3, 4, 3, 5, 2 ];

3）array[3]的值为3，说明没被遍历过，接下来遍历下标为3的元素，同时标记已遍历过的元素：array=[-1,-3, 4,-3, 5, 2 ];

4）array[3]的值为-3，说明3已经被遍历过了，即找到了重复的元素。

实现代码如下：

每个数在数组中都有自己的位置，如果一个数是在自己应该在的位置（在本题中它的值就是它的下标，即所在的位置），那永远不会对它进行调换，也就是不会访问到它，除非它就是那个多出的数，那与它相同的数访问到它的时候便就是结果了；如果一个数所在的位置不是它应该待的地方，那它会去找它应该在的位置，在它位置的数也应该去找它应该在的位置，碰到了负数，也就是说已经出现了这个数，所以就得出结果了。

算法性能分析：

上述方法的时间复杂度为O（n），并且没有申请辅助的存储空间。

这个方法的缺点是修改了数组中元素的值，当然也可以在找到重复元素之后对数组进行一次遍历，把数组中的元素改为它的绝对值，以此来恢复对数组的修改。

方法五：环形相遇法

这个方法采用类似于判断单链表是否存在环的方法来求解问题。“判断单链表是否存在环”是一个非常经典的问题，同时单链表可以采用数组实现，此时可以把每个元素值作为next指针指向下一个元素。本题可以转化为“已知一个单链表中存在环，找出环的入口点”。具体思路：将array[i]看作第i个元素的索引，即array[i]-＞array[array[i]]-＞array[array[array[i]]]-＞array[array[array[array[i]]]]-＞…最终形成一个单链表，由于数组a中存在重复元素，则一定存在一个环，且环的入口元素即为重复元素。

该题的关键在于，数组array的大小是n，而元素的范围是[1,n-1]，所以array[0]不会指向自己，进而不会陷入错误的自循环。如果元素的范围中包含0，则该题不可直接采用该方法。以数组序列[1, 3, 4, 2, 5, 3 ]为例。按照上述规则，这个数组序列对应的单链表如下图所示。

从上图可以看出这个链表有环，且环的入口点为3，所以，这个数组中重复元素为3。

在实现时可以参考求单链表环的入口点的算法：用两个速度不同的变量slow和fast来访问，其中slow 每次前进一步，fast 每次前进两步。在有环结构中，它们总会相遇。接着从数组首元素与相遇点开始分别遍历，每次各走一步，它们必定相遇，且相遇第一点为环入口点。

实现代码如下。

程序的运行结果为

算法性能分析：

上述方法的时间复杂度为O（n），并且没有申请辅助的存储空间。

当数组中的元素不合理时，上述算法有可能会有数组越界的可能性，因此，为了安全性和健壮性，可以在执行fast = array[array[fast]]; slow = array[slow];操作的时候分别检查array[slow]与array[fast]的值是否会越界，如果越界，则说明提供的数据不合法。

引申：对于一个给定的自然数N，有一个N+M个元素的数组，其中存放了小于或等于N的所有自然数，求重复出现的自然数序列{X}。

分析与解答：

对于这个扩展需要，在方法五的基础上，已经标记过的数字在后面一定不会再访问到，除非它是重复的数字。也就是说，只要每次将重复数字中的一个改为靠近N+M的自然数，让遍历能访问到数组后面的元素，就能将整个数组遍历完。此种方法非常不错，而且它具有可扩展性。

实现代码如下：

程序的运行结果为

算法性能分析:

上述方法的时间复杂度为O（n），并且没有申请辅助的存储空间。

当数组中的元素不满足题目要求时，上述方法有可能会有数组越界的可能性，也有可能会进入死循环，为了避免这种情况发生，可以增加适当的安全检查代码。

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

难度系数：★★★☆☆

被考查系数：★★★★☆

题目描述：

给定数组a1, a2, a3, …, an，要求找出数组中的最大值和最小值。假设数组中的值两两各不相同（以自然数数组[1, 2, 3, 4, 5, 6, 7, 8, 9]为例）。

分析与解答：

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

方法一：蛮力法

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

实现代码如下：

程序的运行结果为

算法性能分析:

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

方法二：分治法

分治法就是将一个规模为n的、难以直接解决的大问题，分割为k个规模较小的子问题，采取各个击破、分而治之的策略得到各个子问题的解，然后将各个子问题的解进行合并，从而得到原问题的解的一种方法。

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

实现代码如下：

＜？php function getmaxmin（$arr,$len,&$max,&$min）{if（!$arr||$len＜1）{

程序的运行结果为

方法三：变形的分治法

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

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

实现代码如下：

程序的运行结果为

算法性能分析：

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

7.3 如何找出旋转数组的最小元素

难度系数：★★★☆☆

被考查系数：★★★★☆

题目描述：

把一个有序数组最开始的若干个元素搬到数组的末尾，称之为数组的旋转。输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。例如，数组[3, 4, 5, 1, 2]为数组[1, 2, 3, 4, 5]的一个旋转，该数组的最小值为1。

分析与解答：

其实这是一个非常基本和常用的数组操作，它的描述如下：

有一个有序数组X[0…n-1]，现在把它分为两个子数组：x1[0…m]和x2[m+1…n-1]，交换这两个子数组，使数组x由x1x2变成x2x1，例如x=[1, 2, 3, 4, 5, 6, 7, 8, 9]，x1=[1, 2, 3, 4, 5]， x2=[6, 7, 8, 9]，交换后，x=[6, 7, 8, 9, 1, 2, 3, 4, 5]。

对于本题的解决方案，最容易想到的，也是最简单的方法就是直接遍历法。但是这种方法显然没有用到题目中旋转数组的特性，因此，它的效率比较低。下面介绍一种比较高效的二分查找法。

通过数组的特性可以发现，数组元素首先是递增的，然后突然下降到最小值，再递增。虽然如此，但是还有下面三种特殊情况需要注意：

1）数组本身是没有发生过旋转的，是一个有序的数组，如序列[1, 2, 3, 4, 5, 6]。

2）数组中元素值全部相等，如序列[1, 1, 1, 1, 1, 1]。

3）数组中元素值大部分都相等，如序列[1, 0, 1, 1, 1, 1]。

通过旋转数组的定义可知，经过旋转之后的数组实际上可以划分为两个有序的子数组，前面的子数组的元素值都大于或者等于后面子数组的元素值。可以根据数组元素的这个特点，采用二分查找的思想不断缩小查找范围，最终找出问题的解决方案。

按照二分查找的思想，给定数组arr，首先定义两个变量low和high，分别表示数组的第一个元素和最后一个元素的下标。按照题目中对旋转规则的定义，第一个元素应该是大于或者等于最后一个元素的（当旋转个数为0，即没有旋转时，要单独处理，直接返回数组第一个元素）。接着遍历数组中间的元素arr[mid]，其中mid=（high+low）/2。

1）如果arr[mid]＜arr[mid-1]，则arr[mid]一定是最小值；

2）如果arr[mid+1]＜arr[mid]，则arr[mid+1]一定是最小值；

3）如果arr[high]＞arr[mid]，则最小值一定在数组左半部分；

4）如果arr[mid]＞arr[low]，则最小值一定在数组右半部分；

5）如果arr[low]=arr[mid]且arr[high]=arr[mid]，则此时无法区分最小值是在数组的左半部分还是右半部分（例如，[2, 2, 2, 2, 1, 2]，[2, 1, 2, 2, 2, 2, 2]）。在这种情况下，只能分别在数组的左右两部分找最小值minL与minR，最后求出minL与minR的最小值。

实现代码如下：

程序的运行结果为

算法性能分析：

一般而言，二分查找的时间复杂度为O（log₂ⁿ），对于这道题而言，大部分情况下时间复杂度为O（logn），只有每次都满足上述条件5）的时候才需要对数组中所有元素都进行遍历，因此，这个算法在最坏的情况下的时间复杂度为O（n）。

引申：如何实现旋转数组功能？

分析与解答：

先分别把两个子数组的内容交换，然后把整个数组的内容交换，即可得到问题的解。

以数组x1[1, 2, 3, 4, 5]与数组x2[6, 7, 8, 9]为例，交换两个数组后，x1=[5, 4, 3, 2, 1]，x2=[9, 8, 7, 6]，即x=[5, 4, 3, 2, 1, 9, 8, 7, 6]。交换整个数组后，x=[6, 7, 8, 9, 1, 2, 3, 4, 5]。

实现代码如下：

程序的运行结果为

算法性能分析：

由于这个方法需要遍历两次数组，因此，它的时间复杂度为O（n）。而交换两个变量的值，只需要使用一个辅助储存空间，所以，它的空间复杂度为O（1）。

7.4 如何找出数组中丢失的数

难度系数：★★☆☆☆

被考查系数：★★★☆☆

题目描述：

给定一个由n-1个整数组成的未排序的数组序列，其元素都是1～n中的不同的整数。请写出一个寻找数组序列中缺失整数的线性时间算法。

分析与解答：

方法一：累加求和

首先分析一下数学性质。假设缺失的数字是X，那么这n-1个数一定是1～n之间除了X以外的所有数。试想一下，1～n一共n个数的和是可以求出来的，数组中的元素的和也是可以求出来的，两者相减，其值是不是就是缺失的数字X的值呢？

为了更好地说明上述方法，举一个简单的例子加以说明。假设数组序列为[2, 1, 4, 5]一共4个元素，n的值为5，要想找出这个缺失的数字，可以首先对1～5五个数字求和，求和结果为15（1+2+3+4+5=15），而数组元素的和为array[0]+array[1]+array[2]+array[3]=2+1+4+5= 12，所以，缺失的数字为15-12=3。

通过上面的例子可以很容易形成以下具体思路：定义两个数suma与sumb，其中，suma表示的是这n-1个数的和，sumb 表示的是这n个数的和，很显然，缺失的数字的值即为sumb-suma的值。

实现代码如下：

程序的运行结果为

算法性能分析：

这个方法的时间复杂度为O（n）。需要注意的是，在求和的过程中，计算结果有溢出的可能性。所以，为了避免这种情况的发生，在进行数学运算时，可以考虑位运算，毕竟位运算性能最好，下面介绍如何用位运算来解决这个问题。

方法二：异或法

在解决这个问题前，首先回顾一下异或运算的性质。简单地说，在进行异或运算时，当参与运算的两个数相同时，异或结果为假，当参与异或运算的两个数不相同时，异或结果为真。

1～n这n个数异或的结果为a=1^2^3^…^n。假设数组中缺失的数为m，那么数组中这n-1个数异或的结果为b=1^2^3^…（m-1）^（m+1）^…^n。由此可知，a^b=（1^1）^（2^2）^…（m-1）^（m-1）^m^（m+1）^（m+1）^…^（n^n）=m。根据这个公式可以得知本题的主要思路：定义两个数a与b，其中，a表示的是1到n这n个数的异或运算结果，b表示的是数组中的n-1个数的异或运算结果，缺失的数字的值即为a^b的值。

实现代码如下：

算法性能分析：

这个方法在计算a的时候对数组进行了一次遍历，时间复杂度为O（n），接着在计算b的时候循环执行的次数为N，时间复杂度也为O（n）。因此，这个算法的时间复杂度为O（n）。

7.5 如何找出数组中出现奇数次的数

难度系数：★★★☆☆

被考查系数：★★★★☆

题目描述：

数组中有n+2个数，其中，n个数出现了偶数次，两个数出现了奇数次（这两个数不相等），请用O（1）的空间复杂度，找出这两个数。注意：不需要知道具体位置，只需要找出这两个数。

分析与解答：

根据异或运算的性质不难发现，任何一个数字异或它自己其结果都等于0。所以，对于本题中的数组元素而言，如果从头到尾依次异或每一个元素，那么异或运算的结果自然也就是那个只出现奇数次的数字，因为出现偶数次的数字会通过异或运算全部消掉。

但是通过异或运算，也仅仅只是消除掉了所有出现偶数次数的数字，最后异或运算的结果肯定是那两个出现了奇数次的数异或运算的结果。假设这两个出现奇数次的数分别为a 与b，根据异或运算的性质，将二者异或运算的结果记为c，由于a与b不相等，所以，c的值自然也不会为0。此时只需知道c对应的二进制数中某一个位为1的位数n。例如，十进制数44可以由二进制0010 1100表示，此时可取n=2或者3，或者5，然后将c与数组中第n位为1的数进行异或，异或结果就是a、b中的一个，然后用c异或其中一个数，就可以求出另外一个数了。

通过上述方法为什么就能得到问题的解呢？其实很简单，因为c中第n位为1表示a或b中有一个数的第n位也为1，假设该数为a，那么当将c与数组中第n位为1的数进行异或时，也就是将x与a外加上其他第n位为1的出现过偶数次的数进行异或，化简即为x与a异或，结果即为b。

以数组[3, 5, 6, 6, 5, 7, 2, 2]为例，实现代码如下：

程序的运行结果为

算法性能分析：

这个方法首先对数组进行了一次遍历，其时间复杂度为O（n），接着找result 对应二进制数中位值为1的位数，时间复杂度为O（1），接着又遍历了一次数组，时间复杂度为O（n），因此，这个算法整体的时间复杂度为O（n）。

7.6 如何找出数组中第k小的数

难度系数：★★★★☆

被考查系数：★★★★☆

题目描述：

给定一个整数数组，如何快速地求出该数组中第k小的数。假如数组为[4, 0, 1, 0, 2, 3]，那么第三小的元素是1。

分析与解答：

由于对一个有序的数组而言，能非常容易地找到数组中第k 小的数，因此，可以通过对数组进行排序的方法来找出第k小的数。同时，由于只要求第k小的数，没有必要对数组进行完全排序，只需要对数组进行局部排序就可以了。下面分别介绍几种不同的实现方法。

方法一：排序法

最简单的方法就是首先对数组进行排序，在排序后的数组中，下标为k-1的值就是第k小的数。例如，对数组[4, 0, 1, 0, 2, 3]进行排序后的序列变为[0, 0, 1, 2, 3, 4]，第三小的数就是排序后数组中下标为2对应的数：1。由于最高效的排序算法（如快速排序）的平均时间复杂度为O（nlogn），因此，该方法的平均时间复杂度为O（nlogn），其中n为数组的长度。

方法二：部分排序法

由于只需要找出第k 小的数，因此，没必要对数组中所有的元素进行排序，可以采用部分排序的方法。具体思路：通过对选择排序进行改造，第一次遍历从数组中找出最小的数，第二次遍历从剩下的数中找出最小的数（在整个数组中是第二小的数），第k次遍历就可以从n-k+1（n 为数组的长度）个数中找出最小的数（在整个数组中是第k 小的）。这个算法的时间复杂度为O（n×k）。当然也可以采用堆排序进行k趟排序找出第k小的值。

方法三：类快速排序方法

快速排序的基本思想：将数组array[low…high]中某一个元素（取第一个元素）作为划分依据，然后把数组划分为三部分：①array[low…i-1]（所有的元素的值都小于或等于array[i]），②array[i]，③array[i+1…high]（所有的元素的值都大于array[i]）。在此基础上可以用下面的方法求出第k小的元素：

1）如果i-low=k-1，说明array[i]就是第k小的元素，那么直接返回array[i]；

2）如果i-low＞k-1，说明第k小的元素肯定在array[low…i-1]中，那么只需要递归地在array[low…i-1]中找第k小的元素即可；

3）如果i-low＜k-1，说明第k小的元素肯定在array[i+1…high]中，那么只需要递归地在array[i+1…high]中找第k-（i-low）-1小的元素即可。

对于数组[4, 0, 1, 0, 2, 3]，第一次划分为下面三部分：

接下来需要在{3, 0, 1, 0, 2}中找第三小的元素，把[3, 0, 1, 0, 2]划分为三部分：

接下来需要在[2, 0, 1, 0]中找第三小的元素，把[2, 0, 1, 0]划分为三部分：

接下来需要在[0, 0, 1]中找第三小的元素，把[0, 0, 1]划分为三部分：

此时i=1，low=0；（i-1=1）＜（k-1=2），接下来需要在{1}中找第k-（i-low）-1=1小的元素即可。显然，[1]中第1小的元素就是1。

实现代码如下：

程序的运行结果为

算法性能分析：

快速排序的平均时间复杂度为O（nlogn）。快速排序需要对划分后的所有子数组继续排序处理，而本方法只需要取划分后的其中一个子数组进行处理即可，因此，平均时间复杂度肯定小于O（nlogn）。由此可以看出，这个方法的效率要高于方法一。但是这个方法也有缺点：它改变了数组中数据原来的顺序。当然可以申请额外的n（其中，n为数组的长度）个空间来解决这个问题，但是这样做会增加算法的空间复杂度，所以，通常做法是根据实际情况选取合适的方法。

引申：在O（n）时间复杂度内查找数组中前三名。

分析与解答：

这道题可以转换为在数组中找出前k大的值（例如，k=3）。

如果没有时间复杂度的要求，可以首先对整个数组进行排序，然后根据数组下标就可以非常容易地找出最大的三个数，即前三名。由于这种方法的效率高低取决于排序算法的效率高低，因此，这种方法在最好的情况下时间复杂度都为O（nlogn）。

通过分析发现，最大的三个数比数组中其他的数都大。因此，可以采用类似求最大值的方法来求前三名。具体实现思路：初始化前三名（r1：第一名，r2：第二名，r3：第三名）为数组的第一个元素。然后开始遍历数组：

1）如果当前值tmp大于r1：r3=r2，r2=r1，r1=tmp;

2）如果当前值tmp大于r2且不等于r1：r3=r2，r2=tmp；

3）如果当前值tmp大于r3且不等于r2：r3=tmp。

实现代码如下：

程序的运行结果为

算法性能分析：

这个方法虽然能够在O（n）的时间复杂度求出前三名，但是当k取值很大的时候，比如求前10名，这种方法就不是很好了。比较经典的方法就是维护一个大小为k的堆来保存最大的k个数。具体思路为：维护一个大小为k的小顶堆用来存储最大的k个数，堆顶保存了最小值，每次遍历一个数m，如果m比堆顶元素小，那么说明m肯定不是最大的k个数，因此，不需要调整堆；如果m比堆顶与元素大，那么用这个数替换堆顶元素，替换后重新调整堆为小顶堆。这种方法的时间复杂度为O（nlog₂^k）。这种方法适用于数据量大的情况。

7.7 如何求数组中两个元素的最小距离

难度系数：★★★★☆

被考查系数：★★★☆☆

题目描述：

给定一个数组，数组中含有重复元素，给定两个数字num1和num2，求这两个数字在数组中出现的位置的最小距离。

分析与解答：

对于这类问题，最简单的方法就是对数组进行双重遍历，找出最小距离，但是这种方法效率比较低。由于在求距离时只关心num1与num2这两个数，因此，只需要对数组进行一次遍历即可，在遍历的过程中分别记录num1或num2的位置就可以非常方便地求出最小距离，下面以数组[4, 5, 6, 4, 7, 4, 6, 4, 7, 8, 5, 6, 4, 3, 10, 8]为例，分别介绍这两种实现方法。

方法一：蛮力法

主要思路为：对数组进行双重遍历，外层循环遍历查找num1，只要找到num1，就开始内层循环，即对数组从头开始遍历查找num2，当遍历到num2时，就计算它们的距离dist。当遍历结束后，最小的dist值就是它们之间的最小距离。实现代码如下：

程序的运行结果为

算法性能分析：

这个算法需要对数组进行两次遍历，因此，时间复杂度为O（n²）。

方法二：动态规划

上述方法一的内层循环对num2的位置进行了很多次重复的查找。但是，可以采用动态规划的方法把每次遍历的结果都记录下来从而可以减少遍历次数。具体实现思路：遍历数组，会遇到以下两种情况：

1）当遇到num1时，记录下num1值对应的数组下标的位置lastPos1，通过求lastPos1与上次遍历到num2下标的位置的值lastPos2的差可以求出最近一次遍历到的num1与num2的距离。

2）当遇到num2时，同样记录下它在数组中下标的位置lastPos2，然后通过求lastPos2与上次遍历到num1的下标值lastPos1，求出最近一次遍历到的num1与num2的距离。

假设给定数组为：[4, 5, 6, 4, 7, 4, 6, 4, 7, 8, 5, 6, 4, 3, 10, 8]，num1=4，num2=8。根据以上方法，执行过程如下：

1）在遍历时首先会遍历到4，下标为lastPos1=0，由于此时还没有遍历到num2，因此，没必要计算num1与num2的最小距离；

2）接着往下遍历，又遍历到num1=4，更新lastPos1=3；

3）接着往下遍历，又遍历到num1=4，更新lastPos1=7；

4）接着往下遍历，又遍历到num2=8，更新lastPos2=9；此时由于前面已经遍历到过num1，因此，可以求出当前num1与num2的最小距离为|lastPos2-lastPos1|=2；

5）接着往下遍历，又遍历到num2=8，更新lastPos2=15；此时由于前面已经遍历到过num1，因此，可以求出当前num1与num2的最小距离为| lastPos2- lastPos1|=8；由于8＞2，所以，num1与num2的最小距离为2。

实现代码如下：

算法性能分析：

这个算法只需要对数组进行一次遍历，因此，时间复杂度为O（n）。

7.8 如何求解最小三元组距离

难度系数：★★★★☆

被考查系数：★★★★☆

题目描述：

已知三个升序整数数组a[l]、b[m]和c[n]，在三个数组中各找一个元素，使得组成的三元组距离最小。三元组距离的定义：假设a[i]、b[j]和c[k]是一个三元组，那么距离为：Distance=max（|a[i]-b[j]|,|a[i]-c[k]|,|b[j]-c[k]|），设计一个求最小三元组距离的最优算法。

分析与解答：

最简单的方法就是找出所有可能的组合，从所有的组合中找出最小的距离，但是显然这种方法的效率比较低下。通过分析发现，当ai≤bi≤ci时，此时它们的距离肯定为Di=ci-ai。此时就没必要求bi-ai与ci-ai的值了，从而可以省去很多没必要的步骤，下面分别以三个具体数组为例详细介绍这两种方法。

方法一：蛮力法

最容易想到的方法就是分别遍历三个数组中的元素，对遍历到的元素分别求出它们的距离，然后从这些值里面查找最小值，实现代码如下：

程序的运行结果为

算法性能分析：

这个方法的时间复杂度为O（l×m×n），显然这个方法没有用到数组升序这一特性，因此，该方法肯定不是最好的方法。

方法二：最小距离法

假设当前遍历到这三个数组中的元素分别为a_i、b_i、c_i，并且a_i≤b_i≤c_i，此时它们的距离肯定为D_i=c_i-a_i，那么接下来可以分如下三种情况讨论：

1）如果接下来求a_i、b_i、c_i+1的距离，由于c_i+1≥c_i，此时它们的距离必定为D_i+1=c_i+1-a_i，显然D_i+1≥D_i，因此，D_i+1不可能为最小距离。

2）如果接下来求a_i、b_i+1、c_i的距离，由于b_i+1≥b_i，如果b_i+1≤c_i，此时它们的距离仍然为D_i+1=c_i-a_i；如果b_i+1＞c_i，那么此时它们的距离为D_i+1=b_i+1-a_i，显然D_i+1≥D_i，因此，D_i+1不可能为最小距离。

3）如果接下来求a_i+1、b_i、c_i的距离，如果a_i+1＜c_i-|c_i-a_i|，此时它们的距离D_i+1=max（c_i-a_i+1, c_i=b_i），显然D_i+1＜D_i，因此，D_i+1有可能是最小距离。

综上所述，在求最小距离的时候只需要考虑第三种情况即可。具体实现思路为：从三个数组的第一个元素开始，首先求出它们的距离minDist，接着找出这三个数中最小数所在的数组，只对这个数组的下标往后移一个位置，接着求三个数组中当前遍历元素的距离，如果比minDist小，则把当前距离赋值给minDist，以此类推，直到遍历完其中一个数组为止。

例如，给定数组： a=[ 3, 4, 5, 7 ,15];b=[ 10, 12, 14, 16, 17 ];c=[ 20, 21, 23, 24, 37, 30 ];

1）首先从三个数组中找出第一个元素3、10、20，显然它们的距离为20-3=17。

2）由于3最小，因此，数组a往后移一个位置，求4、10、20的距离为16，由于16＜17，因此，当前数组的最小距离为16。

3）同理，对数组a后移一个位置。依此类推，直到遍历到15的时候，当前遍历到三个数组中的值分别为15、10、20，最小距离为10。

4）由于10最小，因此，数组b往后移动一个位置遍历12，此时三个数组遍历到的数字分别为15、12、20，距离为8，当前最小距离是8。

5）由于12最小，数组b往后移动一个位置为14，依然是三个数中最小值，往后移动一个位置为16，当前的最小距离变为5，由于15是数组a的最后一个数字，因此，遍历结束，求得最小距离为5。

实现代码如下：

算法性能分析：

采用这种算法最多只需要对三个数组分别遍历一边，因此，时间复杂度为O（l+m+n）。

7.9 如何求数组连续最大和

难度系数：★★★★☆

被考查系数：★★★★★

题目描述：

一个有n个元素的数组，这n个元素既可以是正数也可以是负数，数组中连续的一个或多个元素可以组成一个连续的子数组，一个数组可能有多个这种连续的子数组，求子数组和的最大值。例如，对于数组[1,-2, 4, 8,-4, 7,-1,-5]而言，其最大和的子数组为[4, 8,-4, 7]，最大值为15。

分析与解答：

在笔试、面试中，这是一道非常经典的算法题，有多种解决方法，下面分别从简单到复杂逐个介绍。

方法一：蛮力法

最简单也是最容易想到的方法就是找出所有的子数组，然后求出子数组的和，在所有子数组的和中取最大值。实现代码如下：

程序的运行结果为

算法性能分析:

这个算法的时间复杂度为O（n³），显然效率太低，通过对该方法进行分析发现，许多子数组都重复计算了，鉴于此，下面给出一种优化的方法。

方法二：重复利用已经计算的子数组和

由于Sum[i,j]=Sum[i,j-1]+arr[j]，在计算Sum[i,j]时可以使用前面已计算出的Sum[i, j-1]而不需要重新计算，采用这种方法可以省去计算Sum[i,j-1]的时间，因此，可以提高程序的效率。

实现代码如下：

算法性能分析：

这个方法使用了双重循环，因此，时间复杂度为O（n²）。

方法三：动态规划方法

可以采用动态规划的方法来降低算法的时间复杂度。实现思路如下：

首先可以根据数组的最后一个元素arr[n-1]与最大子数组的关系分为以下三种情况讨论：

1）最大子数组包含arr[n-1]，即最大子数组以arr[n-1]结尾。

2）arr[n-1]单独构成最大子数组。

3）最大子数组不包含arr[n-1]，那么求arr[1…n-1]的最大子数组可以转换为求arr[1…n-2]的最大子数组。

通过上述分析可以得出如下结论：假设已经计算出子数组arr[1…i-2]的最大的子数组和All[i-2]，同时也计算出arr[0…i-1]中包含arr[i-1]的最大的子数组和为End[i-1]。则可以得出如下关系：All[i-1]=max（End[i-1],arr[i-1],All[i-2]）。利用这个公式和动态规划的思想可以得到如下代码：

算法性能分析：

与前面几个方法相比，这种方法的时间复杂度为O（n），显然效率更高，但是由于在计算的过程中额外申请了两个数组，因此，该方法的空间复杂度也为O（n）。

方法四：优化的动态规划方法

方法三中每次其实只用到了End[i-1]与All[i-1]，而不是整个数组中的值，因此，可以定义两个变量来保存End[i-1]与All[i-1]的值，并且可以反复利用。实现代码如下：

算法性能分析：

这个方法在保证了时间复杂度为O（n）的基础上，把算法的空间复杂度也降到了O（1）。

引申：在知道子数组最大值后，如何才能确定最大子数组的位置。

分析与解答：

为了得到最大子数组的位置，首先介绍另外一种计算最大子数组和的方法。在上例的方法三中，通过对公式End[i] = max（End[i-1]+arr[i],arr[i]）的分析可以看出，当End[i-1]＜0时， End[i]=array[i]，其中End[i]表示包含array[i]的子数组和，如果某一个值使得End[i-1]＜0，那么就从arr[i]重新开始。可以利用这个性质非常容易地确定最大子数组的位置。

实现代码如下：

程序的运行结果为

7.10 如何求数组中绝对值最小的数

难度系数：★★★★☆

被考查系数：★★★☆☆

题目描述：

有一个升序排列的数组，数组中可能有正数、负数或0，求数组中元素的绝对值最小的数。例如，数组[-10,-5,-2, 7, 15, 50]，该数组中绝对值最小的数是-2。

分析与解答：

可以对数组进行顺序遍历，对每个遍历到的数求绝对值进行比较就可以很容易地找出数组中绝对值最小的数；本题中，由于数组是升序排列的，那么绝对值最小的数一定在正数与非正数的分界点处，利用这种方法可以省去很多求绝对值的操作。下面会详细介绍这几种求解方法。

方法一：顺序比较法

最简单的方法就是从头到尾遍历数组元素，对每个数字求绝对值，然后通过比较就可以找出绝对值最小的数。

以数组[-10,-5,-2, 7, 15, 50]为例，实现方式如下：

1）首先遍历第一个元素-10，其绝对值为10，所以，当前最小值为min=10。

2）遍历第二个元素-5，其绝对值为5，由于5＜10，因此，当前最小值min=5。

3）遍历第三个元素-2，其绝对值为2，由于2＜5，因此，当前最小值为min=2。

4）遍历第四个元素7，其绝对值为7，由于m＞2，因此，当前最小值min还是2。

5）以此类推，直到遍历完数组为止就可以找出绝对值最小的数为-2。

实现代码如下：

程序的运行结果为

算法性能分析：

该方法的平均时间复杂度为O（n），空间复杂度为O（1）。

方法二：数学性质法

在求绝对值最小的数时可以分为如下三种情况：①如果数组第一个元素为非负数，那么绝对值最小的数肯定为数组第一个元素；②如果数组最后一个元素的值为负数，那么绝对值最小的数肯定是数组的最后一个元素；③如果数组中既有正数又有负数，首先找到正数与负数的分界点，如果分界点恰好为0，那么0就是绝对值最小的数。否则，通过比较分界点左右的正数与负数的绝对值来确定最小的数。

那么如何来查找正数与负数的分界点呢？最简单的方法仍然是顺序遍历数组，找出第一个非负数（前提是数组中既有正数又有负数），接着通过比较分界点左右两个数的值来找出绝对值最小的数。这种方法在最坏的情况下时间复杂度为O（n）。下面主要介绍采用二分法来查找正数与负数的分界点的方法。主要思路：取数组中间位置的值a[mid]，并将它与0值比较，比较结果分为以下三种情况：

1）如果a[mid]=0，那么这个数就是绝对值最小的数。

2）如果a[mid]＞0，a[mid-1]＜0，那么就找到了分界点，通过比较a[mid]与a[mid-1]的绝对值就可以找到数组中绝对值最小的数；如果a[mid-1]=0，那么a[mid-1]就是要找的数；否则接着在数组的左半部分查找。

3）如果a[mid]＜0，a[mid+1]＞0，那么通过比较a[mid]与a[mid+1]的绝对值即可；如果a[mid+1]=0，那么a[mid+1]就是要查找的数。否则接着在数组的右半部分继续查找。

为了更好地说明以上方法，可以参考以下几个示例进行分析：

1）如果数组为[1, 2, 3, 4, 5, 6, 7]，由于数组元素全部为正数，而且数组是升序排列，所以，此时绝对值最小的元素为数组的第一个元素1。

2）如果数组为[-7,-6,-5,-4,-3,-2,-1]，此时数组长度length的值为7，由于数组元素全部为负数，而且数组是升序排列，此时绝对值最小的元素为数组的第length-1个元素，该元素的绝对值为1。

3）如果数组为[-7,-6,-5,-3,-1, 2, 4]，此时数组长度length为7，数组中既有正数，也有负数。此时采用二分查找法，判断数组中间元素的符号。中间元素的值为-3，小于0，所以判断中间元素后面一个元素的符号，中间元素后面的元素的值为-1，小于0。因此，绝对值最小的元素一定位于右半部分数组[-1, 2, 4]中，继续在右半部分数组中查找，中间元素为2大于0，2前面一个元素的值为-1，小于0。所以，-1与2中绝对值最小的元素即为所求的数组的绝对值最小的元素的值，所以，数组中绝对值最小的元素的值为-1。

实现代码如下：

程序的运行结果为

算法性能分析：

通过上面的分析可知，由于采取了二分查找的方式，算法的平均时间复杂度得到了大幅降低，为O（nlog₂ⁿ）。其中，n为数组的长度。

7.11 如何找出数组中出现一次的数

难度系数：★★★☆☆

被考查系数：★★★☆☆

题目描述：

一个数组里，除了三个数是唯一出现的，其余的数都出现偶数次，找出这三个数中的任意一个。比如，数组序列为[1, 2, 4, 5, 6, 4, 2]，只有1、5、6这三个数字是唯一出现的，数字2与4均出现了偶数次（2次），只需要输出数字1、5、6中的任意一个就可以。

分析与解答：

根据题目描述可以得到如下几个有用的信息：

1）数组中元素个数一定是奇数个；

2）由于只有三个数字出现过一次，显然这三个数字不相同，因此，这三个数对应的二进制数也不可能完全相同。

由此可知，必定能找到二进制数中的某一个bit来区分这三个数（这一个bit的取值或者为0，或者为1），当通过这一个bit的值对数组进行分组时，这三个数一定可以被分到两个子数组中，并且其中一个子数组中分配了两个数字，而另一个子数组分配了一个数字，而其他出现两次的数字肯定是成对出现在子数组中的。此时只需要重点关注哪个子数组中分配了这三个数中的其中一个，就可以很容易地找出这个数字了。当数组被分成两个子数组时，这一个bit的值为1的数被分到一个子数组subArray1，这一个bit的值为0的数被分到另外一个子数组subArray0。

1）如果subArray1中元素个数为奇数个，那么对subArray1中的所有数字进行异或操作；由于a^a=0，a^0=a，出现两次的数字通过异或操作得到的结果为0，然后再与只出现一次的数字执行异或操作，得到的结果就是只出现一次的数字。

2）如果subArray0中元素个数为奇数个，那么对subArray0中所有元素进行异或操作得到的结果就是其中一个只出现一次的数字。

为了实现上面的思路，必须先找到能区分这三个数字的bit，根据以上的分析给出本算法的实现思路：以32位平台为例，一个int类型的数字占用32位空间，从右向左使用每一位对数组进行分组，分组的过程中，计算这个bit 值为0的数字异或的结果result0，出现的次数count0；这个bit值为1的所有数字异或的结果result1，出现的次数count1。

如果count0是奇数且result1！=0，那么说明这三个数中的其中一个被分配到这一bit为0的子数组中了，因此，这个子数组中所有数字异或的值result0一定是出现一次的数字。如果result1==0，说明这一个bit 不能用来区分这三个数字，此时这三个数字都被分配到子数组subArray0中了，因此，result1！=0就可以确定这一个bit可以被用来区分这三个数字的。

同理，如果count1是奇数且result0!=0，那么result1就是其中一个出现一次的数。

以[6,3,4,5,9,4,3]为例，出现一次的数字为6（110）、5（101）、9（1001），从右向左第一位就可以区分这三个数字，用这个bit 可以把数字分成两个子数组subArray0=[6,4,4]和subArray1=[3,5,9,3]。subArray1中所有元素异或的值不等于0，说明出现一次的数字一定在subArray1中出现了，而subArray0中元素个数为奇数个，说明出现一次的数字，其中只有一个被分配到subArray0中了。所以，subArray0中所有元素异或的结果一定就是这个出现一次的数字6。实现代码如下：

程序的运行结果为

算法性能分析：

这个方法使用了两层循环，总共循环执行的次数为32×N（N为数组的长度），因此，算法的时间复杂度为O（n）。

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

难度系数：★★★★☆

被考查系数：★★★☆☆

题目描述：

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

分析与解答：

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

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

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

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

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

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

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

以上默认此数组序列长度为奇数，如果为偶数就是调用上述方法两次找到中间的两个数求平均。以数组[7, 5, 3, 1, 11, 9]为例，实现代码如下：

程序的运行结果为

算法性能分析：

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

7.13 如何求集合的所有子集

难度系数：★★★★☆

被考查系数：★★★☆☆

题目描述：

有一个集合，求其全部子集（包含集合自身）。给定一个集合S，它包含两个元素＜a,b＞，其全部的子集为＜a,ab,b＞。

分析与解答：

根据数学性质分析，不难得知，子集个数Sn与原集合元素个数n之间的关系满足如下等式：Sn=2ⁿ-1。

具体步骤如下：

1）构造一个和集合一样大小的数组A，分别与集合中的某个元素对应。数组A中的元素只有两种状态：“1”和“0”，代表子集中的对应元素是否要输出，这样数组A可以看作是原集合的一个标记位图。

2）数组A模拟整数“加1”的操作，每执行“加1”操作之后，就将原集合中所有与数组A中值为“1”的相对应的元素输出。

设原集合为＜a,b,c,d＞，数组A的某次“加1”后的状态为[1,0,1,1]，则本次输出的子集为＜a,c,d＞。使用非递归的思想，如果有一个数组，大小为n，那么就使用n 位的二进制，如果对应的位为1，那么就输出这个位，如果对应的位为0，那么就不输出这个位。

例如，集合{a, b, c}的所有子集可如下表所示。

算法的重点是模拟数组加1的操作。数组可以一直加1，直到数组内所有元素都是1。实现代码如下：

程序的运行结果为

该方法的缺点在于如果数组中有重复数时，这种方法将会得到重复的子集。

算法性能分析：

上述算法的时间复杂度为O（n×2ⁿ），空间复杂度O（n）。

7.14 如何对数组进行循环移位

难度系数：★★★☆☆

被考查系数：★★★☆☆

题目描述：

把一个含有n 个元素的数组循环右移K（K是正数） 位，要求时间复杂度为O（n），且只允许使用两个附加变量。

分析与解答：

由于有空间复杂度的要求，因此，只能在原数组中就地进行右移。

方法一：蛮力法

蛮力法也是最简单的方法，题目中需要将数组元素循环右移K位，只需要每次将数组中的元素右移一位，循环K次即可。例如，假设原数组为abcd1234，那么按照此种方式，具体移动过程：abcd1234→4abcd123→34abcd12→234abcd1→1234abcd。

此种方法也很容易写出代码。以数组[1, 2, 3, 4, 5, 6, 7, 8]为例，实现代码如下：

程序的运行结果为

以上方法虽然可以实现数组的循环右移，但是由于每移动一次，其时间复杂度就为O（n）。所以，移动K次，其总的时间复杂度为O（K×n），0＜K＜n，与题目要求的O（n）不符合，需要继续往下探索。

对于上述代码，需要考虑到，K不一定小于n，有可能等于n，也有可能大于n。当K＞n时，右移K-n之后的数组序列跟右移K位的结果一样；当K＞n时，右移K位与右移K'（其中K'=K%n）位等价，根据以上分析，相对完备的代码如下：

算法性能分析：

上例中，算法的时间复杂度为O（n²），与K值无关，但时间复杂度仍然太高，是否还有其他更好的方法呢？

仔细分析上面的方法，不难发现，上述方法的移动采取的是一步步移动的方式，由于题目中已经告知了需要移动的位数为K，为什么不能一步到位呢？

方法二：空间换时间法

通常情况下，以空间换时间往往能够降低时间复杂度，本题也不例外。

首先定义一个辅助数组T，把数组A的第n-K+1到n位数组中的元素存储到辅助数组T中，然后再把数组A中的第1到n-K位数组元素存储到辅助数组T中，然后将数组T中的元素复制回数组A，这样就完成了数组的循环右移，此时的时间复杂度为O（n）。

虽然时间复杂度满足要求，但是空间复杂度却提高了，由于需要创建一个新的数组，所以，此时的空间复杂度为O（n），鉴于此，还可以对此方法继续优化。

方法三：翻转法

把数组看成由两段组成的，记为XY。左旋转相当于要把数组XY变成YX。先在数组上定义一种翻转的操作，就是翻转数组中数字的先后顺序。把X翻转后记为X^T。显然有（X^T）^T=X。

首先对X和Y两段分别进行翻转操作，这样就能得到X^TY^T。接着再对X^TY^T进行翻转操作，得到（X^TY^T）^T=（Y^T）^T（X^T）^T=YX。正好是期待的结果。

回到原来的题目。要做的仅仅是把数组分成两段，再定义一个翻转子数组的函数，按照前面的步骤翻转三次就行了。时间复杂度和空间复杂度都符合要求。

对于数组序列A={123456}，如何实现对其循环右移两位的功能呢？将数组A分成两个部分：A[0～n-K-1]和A[n-K～n-1]，将这两个部分分别翻转，然后放在一起再翻转（反序）。具体步骤：

1）翻转1234：123456→432156。

2）翻转56：432156→432165。

3）翻转432165：432165→561234。

实现代码如下：

算法性能分析：

这个算法的时间复杂度为O（n）。主要是完成翻转（逆序）操作，并且只用了一个辅助空间。

引申：上述问题中K不一定为正整数，有可能为负整数。当K为负整数时，右移K位，可以理解为左移（-K）位，所以，此时可以将其转换为能够求解的情况。

7.15 如何在有规律的二维数组中进行高效的数据查找

难度系数：★★★☆☆

被考查系数：★★★★☆

题目描述：

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。实现一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

例如，下面的二维数组就是符合这种约束条件的。在这个数组中查找数字7，如果数组中含有该数字，那么返回true；在这个数组中查找数字5，如果数组中不含有该数字，那么返回false。

分析与解答：

最简单的方法就是对二维数组进行顺序遍历，然后判断待查找元素是否在数组中，这个算法的时间复杂度为O（M×N），其中，M、N分别为二维数组的行数和列数。

虽然上述方法能够解决问题，但这种方法显然没有用到二维数组中数组元素有序的特点，因此，该方法不是最好的方法。

此时需要转换一种思路进行思考，一般情况下，当数组中元素有序时，二分查找是一个很好的方法，对于本题而言，同样适用二分查找，实现思路如下。

给定数组array（行数：rows，列数：columns，待查找元素：data），首先，遍历数组右上角的元素（i=0，j=columns-1），如果array[i][j] = data，那么在二维数组中找到了data，直接返回；如果array[i][j]＞data，那么说明这一列其他的数字也一定大于data。因此，没有必要在这一列继续查找了，通过j--操作排除这一列。同理，如果array[i][j]＜data，那么说明这一行中其他数字也一定比data 小，因此，没有必要再遍历这一行了，可以通过i++操作排除这一行。依此类推，直到遍历完数组结束。

实现代码如下：

程序的运行结果为

算法性能分析：

这个算法主要从二维数组的右上角遍历到左下角，因此，算法的时间复杂度为O（M+N），此外这个算法没有申请额外的存储空间。

7.16 如何寻找最多的覆盖点

难度系数：★★★☆☆

被考查系数：★★★★☆

题目描述：

坐标轴上从左到右依次的点为a[0]、a[1]、a[2]、…、a[n-1]，设一根木棒的长度为L，求L最多能覆盖坐标轴的几个点？

分析与解答：

本题求满足a[j]-a[i]≤L和a[j+1]-a[i]＞L这两个条件的j与i之间所包含的点个数的最大值，即j-i+1最大，这样题目就简单多了。方法：直接从左到右扫描，使用两个索引i和j，i从位置0开始，j从位置1开始，如果a[j]-a[i]≤L，则j++前进，并记录中间经过的点的个数，如果a[j]-a[i]＞L，则j--回退，覆盖点个数-1，回到刚好满足条件的时候，将满足条件的最大值与前面找出的最大值比较，记录下当前的最大值，然后执行i++、j++，直到求出最大的点个数。

有两点需要注意：

1）这里可能不存在i和j使得a[j]-a[i]刚好等于L的情况发生，所以，判断条件不能为a[j]-a[i]=L。

2）可能存在不同的覆盖点但覆盖的长度相同的情况发生，此时只选取第一次覆盖的点。

以数组[1, 3, 7, 8, 10, 11, 12, 13, 15, 16, 17, 19, 25]为例，实现代码如下：

程序的运行结果为

算法性能分析：

这个算法的时间复杂度为O（n），其中，n为数组的长度。

7.17 如何判断请求能否在给定的存储条件下完成

难度系数：★★★☆☆

被考查系数：★★★★☆

题目描述：

给定一台有m个存储空间的机器，有n个请求需要在这台机器上运行，第i个请求计算时需要占R[i]空间，计算结果需要占O[i]个空间（O[i]＜R[i]）。设计一个算法，判断这n个请求能否全部完成？若能，给出这n个请求的安排顺序。

分析与解答：

这道题的主要思路：首先对请求按照R[i]-O[i]由大到小进行排序，然后按照由大到小的顺序进行处理，如果按照这个顺序能处理完，则这n 个请求能被处理完，否则处理不完。那么请求i能完成的条件是什么呢？在处理请求i的时候前面所有的请求都已经处理完成，那么它们所占的存储空间为O（0）+O（1）+…+O（i-1），剩余的存储空间left为left=m-（O（0）+O（1）+…+O（i-1）），要使请求i 能被处理，则必须满足left≥R[i]。只要剩余的存储空间能存放R[i]，那么在请求处理完成后就可以删除请求从而把处理的结果放到存储空间中，由于O[i]＜R[i]，此时必定有空间存放O[i]。

为什么用R[i]-O[i]由大到小的顺序来处理？请看下面的分析：

假设第一步处理R[i]-O[i]最大的值。使用归纳法（假设每一步都取剩余请求中R[i]-O[i]最大的值进行处理），假设n=k时能处理完成，那么当n=k+1时，由于前k个请求是按照R[i]-O[i]从大到小排序的，在处理第k+1个请求时，需要的空间为A=O[1]+…+O[i]+…+O[k]+R[k+1]，只有A≤m时才能处理第k+1个请求。假设把第k+1个请求和前面的某个请求i互换位置，即不按照R[i]-O[i]由大到小的顺序来处理，在这种情况下，第k+1个请求已经被处理完成，接着要处理第i的请求，此时需要的空间为B=O[1]+…+O[i-1]+O[k+1]+O[i+1]+…+R[i]，如果B＞A，则说明按顺序处理成功的可能性更大（越往后处理剩余的空间越小，请求需要的空间越小越好）；如果B＜A，则说明不按顺序更好。根据R[i]-O[i]有序的特点可知：R[i]-O[i]≥R[k+1]-O[k+1]，即O[k+1]+R[i]≥O[i]+R[k+1]，所以，B≥A，因此，可以得出结论：方案B不会比方案A更好。即方案A是最好的方案，也就是说，按照R[i]-O[i]从大到小排序处理请求，成功的可能性最大。如果按照这个序列都无法完成请求序列，那么任何顺序都无法实现全部完成，以数组[10, 15, 23, 20, 6, 9, 7, 16]和数组[2, 7, 8, 4, 5, 8, 6,8]为例，实现代码如下：

程序的运行结果为

算法性能分析：

这个算法的时间复杂度为O（n2）。

7.18 如何按要求构造新的数组

难度系数：★★★☆☆

被考查系数：★★★☆☆

题目描述：

给定一个数组a[N]，构造一个新的数组b[N]，其中，b[i]=a[0]×a[1]×…×a[N-1]/a[i]。在构造数组的过程中，有如下几点要求：

1）不允许使用除法。

2）要求O（1）空间复杂度和O（N）时间复杂度。

3）除遍历计数器与a[N]、b[N]外，不可以使用新的变量（包括栈临时变量、堆空间和全局静态变量等）。

4）请用程序实现并简单描述。

分析与解答：

如果没有时间复杂度与空间复杂度的要求，算法将非常简单，首先遍历一遍数组a，计算数组a中所有元素的乘积，并保存到一个临时变量tmp中，然后再遍历一遍数组a并给数组赋值：b[i]=tmp/a[i]。但是这种方法使用了一个临时变量，因此，不满足题目的要求，下面介绍另外一种方法。

在计算b[i]时，只要将数组a中除了a[i]以外的所有值相乘即可。这种方法的主要思路：首先遍历一遍数组a，在遍历的过程中对数组b进行赋值：b[i]=a[i-1]×b[i-1]，这样经过一次遍历后，数组b的值为b[i]=a[0]×a[1]×…×a[i-1]。此时只需要将数组中的值b[i]再乘以a[i+1]×a[i+2]×…a[N-1]，实现方法为逆向遍历数组a。把数组后半段值的乘积记录到b[0]中，通过b[i]与b[0]的乘积就可以得到满足题目要求的b[i]。具体而言，执行b[i] = b[i]×b[0]（首先执行的目的是为了保证在执行下面一个计算的时候，b[0]中不包含与b[i]的乘积），接着记录数组后半段的乘积到b[0]中：b[0]=b[0]*a[i]。

以数组[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]为例，实现代码如下：

程序的运行结果为

7.19 如何获取最好的矩阵链相乘方法

难度系数：★★★☆☆

被考查系数：★★★☆☆

题目描述：

给定一个矩阵序列，找到最有效的方式将这些矩阵相乘在一起。给定表示矩阵链的数组p []，使得第i个矩阵A i的维数为p [i-1]×p [i]。编写一个函数MatrixChainOrder（），该函数应该返回乘法运算所需的最小乘法数。

输入：p []=[40，20，30，10，30]

输出：26000

有4个大小为40×20、20×30、30×10和10×30的矩阵。假设这4个矩阵为A、B、C和D，并且该函数执行乘法的运算次数要最少。

分析与解答：

该问题实际上并不是执行乘法，而只是决定以哪个顺序执行乘法。由于矩阵乘法是关联的，所以有很多选择来进行矩阵链的乘法运算。换句话说，无论采用哪种方法来执行乘法，结果将是一样的。例如，如果有4个矩阵A、B、C和D，可以有如下几种执行乘法的方法：

（ABC）D=（AB）（CD）=A（BCD）=…

虽然这些方法的计算结果相同。但是，不同的方法需要执行乘法的次数是不相同的，因此效率也是不相同的。例如，假设A是10×30矩阵，B是30×5矩阵，C是5×60矩阵。那么，

（AB）C的执行乘法运算的次数为（10×30×5）+（10×5×60）=1500+3000=4500次。

A（BC）的执行乘法运算的次数为（30×5×60）+（10×30×60）=9000+18000=27000次。

显然，第一种方法需要执行更少的乘法运算，因此效率更高。

对于本题中示例而言，执行乘法运算的次数最少的方法如下：

（A（BC））D的执行乘法运算的次数为20×30×10+40×20×10+40×10×30=26000次

方法一：递归法

最简单的方法就是在所有可能的位置放置括号，计算每个放置的成本并返回最小值。在大小为n的矩阵链中，可以以n-1种方式放置第一组括号。例如，给定的链是4个矩阵，那么有三种方式放置第一组括号：（A）（BCD）、（AB）（CD）和（ABC）（D）。每个括号内的矩阵链可以被看作较小尺寸的子问题。因此，可以使用递归方便地求解。递归的实现代码如下：

程序的运行结果为

这个算法的时间复杂度是指数级的。可以注意到，这种算法会对一些子问题进行重复的计算。例如，在计算（A）（BCD）这种方案时会计算C×D的代价，而在计算（AB）（CD）这种方案的时候又会重复计算C×D的代价。显然子问题是有重叠的，对于这种问题，通常可以用动态规划的方法来降低时间复杂度。

方法二：动态规划法

动态规划的典型方法是使用自下而上的方式来构造临时数组，把子问题的中间结果保存到数组中，从而可以避免大量重复的计算。实现代码如下：

算法性能分析：

这个算法的时间复杂度为O（n3），空间复杂度为O（n2）。

7.20 如何求解迷宫问题

难度系数：★★★★☆

被考查系数：★★★★☆

题目描述：

给定一个大小为n×n的迷宫，一只老鼠需要从迷宫的左上角（对应矩阵的[0][0]）走到迷宫的右下角（对应矩阵的[1][N-1]），老鼠只能向两方向移动：向右或向下。在迷宫中，0表示没有路（是死胡同），1表示有路。例如下图给定下面的迷宫：

图中标粗的路径就是一条合理的路径。请给出算法来找到这样一条合理的路径。

分析与解答：

最容易想到的方法就是尝试所有可能的路径，找出可达的一条路。显然这种方法效率非常低下，这里重点介绍一种效率更高的回溯法。主要思路为：当碰到死胡同的时候，回溯到前一步，然后从前一步出发继续寻找可达的路径。算法的主要框架为：

根据以上框架很容易进行代码实现了。实现代码如下：

程序的运行结果为：

7.21 如何从三个有序数组中找出它们的公共元素

难度系数：★★★☆☆

被考查系数：★★★☆☆

题目描述：

给定以非递减顺序排序的三个数组，找出这三个数组中的所有公共元素。例如，给出下面三个数组：ar1=[2, 5, 12, 20, 45, 85]，ar2=[16, 19, 20, 85, 200]，ar3=[3, 4, 15, 20, 39, 72, 85, 190]。那么这三个数组的公共元素为 [20，85]。

分析与解答：

最容易想到的方法是首先找出两个数组的交集，然后再把这个交集存储在一个临时数组中，最后再找出这个临时数组与第三个数组的交集。这个算法的时间复杂度为O（N1 + N2 +N3），其中N1、N2和N3分别为三个数组的长度。这种方法不仅需要额外的存储空间，而且还需要额外的两次循环遍历。下面介绍另外一种只需要一次循环遍历，而且不需要额外存储空间的方法，主要思路：假设当前遍历的三个数组的元素分别为ar1[i]、ar2[j]、ar3[k]，则存在以下几种可能性。

1）如果ar1[i]、ar2[j]和ar3[k]相等，那么说明当前遍历的元素是三个数组的公有元素，可以直接打印出来，然后通过执行i++、j++、k++，使三个数组同时向后移动，此时继续遍历各数组后面的元素。

2）如果ar1[i]＜ar2[j]，那么执行i++来继续遍历ar1中后面的元素，因为ar1[i]不可能是三个数组公有的元素。

3）如果ar2[j]＜ar3[k]，同理可以通过j++来继续遍历ar2后面的元素。

4）如果前面的条件都不满足，那么说明ar1[i]＞ar2[j]而且ar2[j]＞ar3[k]，此时可以通过k++来继续遍历ar3后面的元素。

实现代码如下：

程序的运行结果为

算法性能分析：

这个算法的时间复杂度为O（N1+N2+N3）。