1.1 数组概述

1.1.1 数组的定义

数组常用于存放序列数据。序列数据（或者线性表）可以表示为 a =[ a ₀ ， a ₁ ，…， a _{n -1} ]，其中有 n 个元素，元素序号（或索引）依次为0～ n -1， a ₀ 为首元素， a _{n -1} 为尾元素， a ₀ 没有前驱元素， a _{n -1} 没有后继元素，其他每个元素有且仅有一个前驱元素和一个后继元素。

从维的角度来看，数组分为一维数组和二维数组等，如图1.1所示，其中二维数组可以看成元素为一维数组的一维数组，以此类推。从实现的角度来看，数组分为固定长度的数组（静态数组）和动态数组，如图1.2所示，固定长度的数组定义简单，但应用不方便，在实际应用中主要使用动态数组。数组的基本操作有存元素（如 a _i = x ）和取元素（ x = a _i ）。

1.1.2 数组的知识点

1.C++中的数组

C++STL提供了vector类模板，其对象就是动态数组（或者向量）。如果在插入元素时超过了空间大小会自动分配更大的空间（通常按2倍大小扩容），不会出现上溢出，这就是动态数组的主要优点。定义vector对象的几种常用方式如下。

C++：

vector向量可以从末尾快速地插入和删除元素，快速地随机访问元素，但在中间插入和删除元素较慢，因为需要移动插入或删除位置后面的所有元素。其主要的成员函数如下。

·　capacity（）：返回向量容器所能容纳的元素的个数。

·　resize（n）：调整向量的容器，使其恰好容纳 n 个元素，增加部分用默认值填充。

·　empty（）：判断向量容器是否为空。

·　size（）：返回向量的长度。

·　[i]：返回向量中下标为 i 的元素。

·　front（）：返回向量的首元素。

·　back（）：返回向量的尾元素。

·　push_back（）：在向量的尾部添加一个元素。

·　insert（pos，e）：在向量的pos位置插入元素e。

·　erase（）：删除向量中某个迭代器或者迭代器区间指定的元素。

·　clear（）：删除向量中的所有元素。

·　begin（）/end（）：用于正向遍历，返回向量中首元素的位置/尾元素的后一个位置。

·　rbegin（）/rend（）：用于反向遍历，返回向量中尾元素的位置/首元素的前一个位置。

其中，容量指一个向量中最多能够存放的元素的个数（capacity（）的返回值），长度表示一个向量中实际存放的元素的个数（size（）的返回值）。例如：

C++：

2.C++中的sort（）排序算法

在算法设计中经常需要排序，C++STL提供了通用排序算法sort（），它适用于数组或vector向量等数据的排序。

1）内置数据类型的排序

对于内置数据类型的数据，sort（）默认以less＜T＞（即小于关系函数）作为关系比较函数实现递增排序，为了实现递减排序，需要调用大于关系函数greater＜T＞。例如：

C++：

2）自定义数据类型的排序

对于自定义数据类型（如结构体或者类），同样默认以less＜T＞（即小于关系函数）作为关系比较函数，但需要重载该函数，用户也可以自定义关系函数。在这些重载函数或者关系函数中指定数据的排序顺序（按哪些结构体成员排序，是递增还是递减）。归纳起来，实现排序主要有以下两种方式。

方式1： 在声明结构体类型或者类中重载＜运算符，以实现按指定成员的递增或者递减排序。例如：

C++：

运行结果：

说明： 学习中可以这样记忆，sort（）默认使用＜运算符实现递增排序，如果重载函数operator＜中是用当前对象的成员no（放在比较运算符的前面）与参数对象s的成员no（放在比较运算符的后面）进行比较，若比较运算符是＜（与operator＜一致），则实现按no递增排序；若比较运算符是＞，则实现按no递减排序。

方式2： 在结构体或类中重载函数调用运算符（），以实现按指定成员递增或者递减排序。例如：

C++：

运行结果：

说明： 在C++11及以上版本中可以使用Lambda表达式更方便地指定排序中的比较方式。

3.Python中的数组

Python中的万能列表可以看成动态数组，其基本形式是在一个方括号内以逗号分隔若干元素。每个元素都有一个位置或索引，索引分为正索引和负索引。例如 a =[1，2，3，4，5，6，7，8，9，10]，其元素个数 n =10，对应的索引如图1.3所示，首元素的值为1，其正索引是0，负索引是-10，以此类推。

列表切片是从原始列表中提取列表的一部分，其基本格式如下：

其中，start为起始索引，默认从0开始，-1为负索引，表示尾元素；end为结束索引（不含）；step为步长，当步长为正时从左向右取值，当步长为负时反向取值。例如：

列表包含的主要方法如下，这些方法是通过列表名称（如列表 a ）调用的。

·　a.clear（）：清空列表 a 。

·　a.append（e）：在列表 a 的末尾添加元素e。

·　a.count（e）：统计元素e在列表 a 中出现的次数。

·　a.index（e）：从列表 a 中找出第一个与e匹配的元素的索引。

·　a.insert（i，e）：将元素e插入列表 a 中索引为 i 的位置。

·　a.pop（[i=-1]）：移除列表 a 中索引为 i 的元素（默认为尾元素），并返回该元素。

·　a.remove（e）：移除列表 a 中第一个与e匹配的元素。

·　a.reverse（）：逆置列表 a 中的元素。

支持列表的主要函数如下，这些函数并不是列表的成员，可以直接调用，但需要在函数参数中指定列表名称（如列表 a ）。

·　len（a）：返回列表 a 中元素的个数。

·　sum（a[，start]）：返回列表 a 中从start位置开始向右的所有元素的和，start默认为0。

·　max（a）：返回列表 a 中元素的最大值。

·　min（a）：返回列表 a 中元素的最小值。

·　list（seq）：将可迭代对象seq转换为列表。

4.Python中列表的排序

Python提供了两种排序方式，即用列表的list.sort（）方法进行排序和用sorted（list）函数进行排序，两者的区别是sorted（list）返回一个对象，可以用作表达式，但原来的list不变，而是生成一个新的排好序的list对象；list.sort（）不会返回对象，直接改变原有的list。list.sort（）的使用格式如下：

其中，key指出用来进行比较的元素；reverse指出排序规则，reverse=True为递减排序，reverse=False为递增排序（默认）。例如：

Python：

对于多关键字排序，key可以使用operator模块提供的itemgetter函数获取对象的哪些维的数据，参数为一些序号，这里的operator.itemgetter函数获取的不是值，而是定义了一个函数，通过该函数作用到对象上才能获取值。另外，也可以使用lambda函数，在需要反序排列的数值关键字前加“-”号。例如：

Python：

5.整体建表法

所谓整体建表，就是一次性建立一个数组中的全部元素，由于元素是一个一个插入的，如果每次将新元素插入前端或者中间，插入一个元素的时间为 O （ n ），这样性能低下，通常是将新元素插入末尾，插入一个元素的时间为 O （1）。如图1.4所示为整体建立ans的示意图。

例如，给定一个整数数组 a ，以下算法返回包含 a 中所有奇数元素的数组。

C++：

Python：

由于push_back（）和append（）的执行时间为 O （1），所以上述算法的时间复杂度为 O （ n ）。在实际应用中可以根据问题要求确定将哪些元素插入结果数组中。

6.基本二路归并法

给定两个递增有序数组 a 和 b ，将所有元素归并到数组 c 中，并且要求 c 中的元素也是递增有序的。该问题有多种解法，最高效的解法是使用基本二路归并法，其过程如下。

（1）分别用 i 、 j 遍历数组 a 和 b （均从0开始），当 i 和 j 都没有超界时循环：比较 a [ i ]和 b [ j ]，若 a [ i ]＜ b [ j ]，则将 a [ i ]添加到 c 中（即归并较小元素 a [ i ]），置 i ++；否则，将 b [ j ]添加到 c 中（即归并较小元素 b [ j ]），置 j ++。

（2）当 i 和 j 中有一个超界时，假设 i 超界，说明 b 中剩余的元素都是较大的元素，将这些元素一一归并到 c 中。

例如， a =[1，5，7，9]， b =[2，3，4，10，12，20]，基本二路归并过程如图1.5所示。首先 i =0， j =0， a [0]＜ b [0]⇨归并 a [0]， c =[1]， i =1； a [1]＞ b [0]⇨归并 b [0]， c =[1，2]， j =1，以此类推，当 i =3， j =3时， a [3]＜ b [3]⇨归并 a [3]， c =[1，2，3，4，5，7，9]， i =4，此时 i 超界，将 b 中剩余的元素归并到 c 中， c =[1，2，3，4，5，7，9，10，12，20]。

使用基本二路归并过程生成归并的元素，并且使用整体建表产生结果数组 c ，对应的算法如下。

C++：

Python：

上述算法的时间复杂度为 O （ m + n ）。

7.二路归并法的扩展应用

这里介绍二路归并法的几种扩展应用方式。

1）求交集

给定两个递增有序数组 a 和 b 表示两个集合，每个集合中的元素不重复，求 a 和 b 的交集，用递增有序数组 c 表示，同时要求数组 c 中的元素不重复。例如， a =[1，2，5，8]， b =[1，3，4，5，8，10]，则 c =[1，5，8]。

使用基本二路归并过程，当 a 和 b 均没有归并完并且比较的两个元素相同时将其添加到结果数组 c 中。这样使用基本二路归并过程生成交集的元素，同时使用整体建表产生结果数组 c ，对应的算法如下。

C++：

Python：

上述算法的时间复杂度为 O （ m + n ）。

2）求差集

给定两个递增有序数组 a 和 b 表示两个集合，每个集合中的元素不重复，求 a - b 的结果（差集），用递增有序数组 c 表示，同时要求数组 c 中的元素不重复。例如， a =[1，2，5，8]， b =[1，3，4，5，8，10]，则 c =[2]。

差集 a - b 的结果包含所有属于 a 但不属于 b 的元素，使用基本二路归并过程，当 a 和 b 均没有归并完并且 a [ i ]＜ b [ j ]时将 a [ i ]添加到结果数组 c 中，当 b 归并完如果 a 没有归并完，则将 a 中剩余的元素添加到 c 中。这样使用基本二路归并过程生成差集的元素，同时使用整体建表产生结果数组 c ，对应的算法如下。

C++：

Python：

3）归并结果除重

给定两个递增有序数组 a 和 b ，每个数组中可能存在重复的元素，求 a 和 b 合并的结果，用递增有序数组 c 表示，同时要求数组 c 中的元素不重复。例如， a =[1，2，5，5，8]， b =[2，2，4，5，8，10]，则 c =[1，2，4，5，8，10]。

使用基本二路归并过程，当生成归并元素 x 时需要与结果数组 c 的末尾元素比较，只有在不相等时将其添加到 c 中，对应的算法如下。

C++：

Python：

8.多路归并法

给定 k （ k ≥3）个非空递增有序数组 a [0.. k -1]，其中 a [ i ]（0≤ i ＜ k ）表示段号为 i 的递增有序数组（归并段 i ），要求将全部元素合并到递增有序数组 c 中。例如， a ={{1，3，5，6}，{1，2，5}，{2，6，8}}， k =3，则 c =[1，1，2，2，3，5，5，6，6，8]。

设计长度为 k 的数组 p 和 x ， p [ i ]用于遍历归并段 i （初始为0）， x [ i ]表示归并段 i 中当前由 p [ i ]指向的元素。先将 a 中 p [ i ]=0（0≤ i ＜ k ）指向的元素存放到 x [ i ]中：

（1）求出 x 中最小元素的段号mini（下标）。

（2）当 x 中的全部元素均为∞时置mini=-1，这种情况说明 a 中的全部元素归并完毕，算法结束。

（3）否则说明当前最小元素所属的段号为mini，最小元素在该归并段中的序号为 p [mini]，将该最小元素添加到结果数组 c 中，执行 p [mini]++将其后移一个位置。若 p [mini]超界，则置 x [ i ]为∞，表示归并段 i 的全部元素归并完毕；否则置 x [mini]为 a [mini][ p [mini]]，即取归并段mini中的下一个元素参与归并。

重复上述过程，直到算法结束。对应的 k 路归并算法如下。

C++：

Python：

上述算法的时间复杂度为 O （ nk ），其中 n 为 k 个段中全部元素个数之和。