《数据结构》保姆级代码大题解析 —— 顺序表

一. 顺序表的定义

顺序表，本质就是线性表的顺序存储结构形式。

它的实现逻辑，是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

顺序表的特点是表中元素的逻辑顺序与其存储的物理顺序相同（顺序存储），且顺序表中元素的位序是从1开始的，而数组中元素的下标是从0开始的。

注意：顺序表的顺序存取结构天然支持随机存取结构，所谓随机存取，访问表里任意位置的元素，耗时都是恒定的，可直接访问表中任意位置的元素，无需从头遍历；而与之相对应的顺序存取结构的访问时间线性，取决于数据的排列顺序，只能顺序访问，不支持直接跳转访问某个位置，是链表的特点之一。

对于易搞混的顺序存储和顺序存取也当作以区分：顺序存储是物理存储结构的概念，描述数据在内存 / 磁盘中的物理空间布局；顺序存取是数据访问方式的概念，描述读写数据的逻辑规则。简单的区分就是顺序存储，说的是数据在内存里挨不挨着；顺序存取，说的是访问数据要不要从头挨个找。

 顺序表的数据存在静态分配和动态分配两种。

静态分配会由于所分配的空间大小已经事先固定，不能二次更改，所以遇到空间占满不够用的情况下，会产生数据溢出导致程序崩溃。

静态分配顺序表定义代码实现如下：

#define MaxSize 100 //定义顺序表数组的最大长度 typedef struct { ElemType data[MaxSize]; //顺序表中的元素 int length; //顺序表的当前长度 }SqList; //静态分配顺序表的名称

而动态分配不同，其通过动态分配语句实时分配空间，在空间占满不够用的情况下可以直接另辟蹊径一块内存空间，并且将源元素如数拷贝到新创建的空间当中，从而达到动态扩容的效果，所以这种操作可以预防为了防止内存不够用而一次性分配大量空间导致空间过剩造成浪费的情况出现。

动态分配顺序表定义代码实现如下：

#define InitSize 100 //定义顺序表数组的初始长度 typedef struct { ElemType *data; //定义顺序表动态分配数组的指针 int MaxSize, length; //动态分配数组的最大容量和当前个数 }SeqList; //动态分配数组顺序表的名称 L.data = (ElemType*) malloc (sizeof (ElemType) * InitSize) ; //动态分配语句

顺序表的优点：

①可进行随机访问，即可通过首地址和元素序号可以在 O(1) 的时间复杂度内找到指定的的元素；

②存储密度高，每个节点只存储数据元素。

对于优点的补充解析：

①定义于顺序存取结构的它说白了就是找元素快。因为它所有元素在内存里都是连续挨着放的，我们只要知道第一个元素的地址，还有单个元素占多大内存，直接就能算出第 n 个或者你想要的目标元素的地址，不用像链表那样必须从头挨个往下找。不管找第 1 个还是第 1000 个元素，耗时都一样，也就是常说的 O (1) 时间复杂度随机访问。

②就是不浪费额外内存，对比链表就特别明显，链表的每个节点除了存数据之外，还得额外占空间存指向下一个节点的不存有效数据的指针，纯额外开销。相比之下顺序表的每一块空间都只存数据本身，同样大的内存，顺序表能装更多的有效数据，内存利用率更高。

顺序表的缺点：

①元素的插入和删除需要移动大量的元素，插入操作平均需要移动 n/2 个元素，删除操作平均需要移动（n/1)/2 个元素。

②顺序存储分配需要一段连续的存储空间，不够灵活。

对于缺点的补充解析：

①比如你有一个存了 100 个元素的顺序表，要是想在最开头插一个新元素，那后面原来的 99 个元素，全都得往后挪一个位置才能空出位置；要是删最开头的元素，后面 99 个又得全都往前挪一位补上空位。数据量越大，要移动的元素就越多，平均下来算一算插删都要动差不多一半的元素，时间复杂度直接到 O (n) ，和链表插删只需要改个指针的 O (1) 的时间复杂度相比效率差太多了。

②顺序表必须要一整块连续的内存空间才能用。比如你要存 1000 个整型数据，就得找一块能刚好放下这 1000 个数据的连续内存，哪怕你内存里零散的空闲空间加起来够大，但凑不成一整块连续的，就用不了。而且我们还得提前预估要多大的空间，预估小了会不够用要扩容，预估大了又会浪费空闲内存，特别不灵活，不像链表的节点可以分散在内存各个角落，随用随申请就行。所以这里有一个动态分配内存的语句：L.data = (ElemType*) malloc (sizeof (ElemType) * InitSize) ;

二. 顺序表的基本操作

1. 顺序表的初始化

给静态顺序表做初始化，把有效元素长度置 0，创建一个空的静态顺序表。

void InitList(SqList& L) { L.length = 0; //令静态分配顺序表的初始长度为0 }

给动态顺序表做初始化，申请初始堆内存，设置初始容量和长度，创建空的动态顺序表。

void InitList(SeqList& L) { L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize); //动态分配空间 L.length = 0; //顺序表的初始长度为0 L.MaxSize = InitSize; //顺序表的初始空间容量 }

给容量不足的动态顺序表扩容，申请更大的新内存、迁移原有数据、释放旧内存，更新表的最大容量。

void IncreaseSize(SeqList& L, int len) { if (L == NULL || len <= 0) //避免非法扩容 { return; } ElemType* p = L.data; //备份旧数组地址 L.data = (ElemType*)malloc((L.MaxSize + len) * sizeof(ElemType)); //申请更大内存 for (int i = 0; i < L.length; i++) //拷贝旧数据到新数组 { L.data[i] = p[i]; } L.MaxSize = L.MaxSize + len; //更新顺序表的空间容量为扩容后的大小 free(p); //释放旧数组内存，避免内存泄漏 }

2. 插入操作

可以指定要插入的位置（第 i 位，从 1 开始数）和要插入的元素 e，函数会先检查插入位置是否合法、顺序表是否还有空位，没问题就把目标位置及后面的元素往后挪，腾出位置放新元素，插入成功返回 true，失败返回 false。

bool ListInsert(SqList& L, int i, ElemType e) { if (i<1 || i>L.length + 1) //判断i的范围是否有效 return false; if (L.length >= MaxSize) //如果当前存储空间已满，则报错 return false; for (int j = L.length; j >= i; j--) //将第i个元素及之后的元素后移 L.data[j] = L.data[j - 1]; L.data[i - 1] = e; //在i位置处放e，位序转数组下标要-1 L.length++; //顺序表的有效元素长度＋1 return true; }

最好情况：在顺序表尾插入元素（i = n + 1），不需要移动任何元素，时间复杂度为 O (1) 。

最坏情况：在顺序表头插入元素（i = 1），需要把表里所有 n 个元素都往后挪一位，时间复杂度为O (n) 。

平均情况：

 ，每个位置插入的概率相同，平均需要移动 n/2 个元素，平均时间复杂度为 O (n) 。

3. 删除操作

可以指定要删除的位置（第 i 位，从 1 开始数），函数会先检查删除位置是否合法，没问题就把被删除的元素通过参数 e 带出来，再把后面的元素往前挪覆盖被删的位置，更新表的长度，删除成功返回 true，失败返回 false。

bool ListDelete(SqList& L, int i, ElemType& e) { if (i<1 || i>L.length) //检查删除的位置是否合法 return false; e = L.data[i - 1]; //先把要删除的元素存到e里，带出去给调用的地方使用 for (int j = 1; j < L.length; j++) //将第i个位置的元素前移 return L.data[j - 1] = L.data[j]; L.length--; //顺序表长度减1 return true; }

最好情况：删除表尾元素（i = n），不需要移动元素，时间复杂度为 O (1) 。

最坏情况：删除表头元素（i = 1），需移动除了表头元素外其他所有元素，时间复杂度为 O (n) 。

平均情况：

，每个位置删除的概率相同，平均需要移动 (n-1)/2 个元素，平均时间复杂度为 O (n) 。

4. 顺序查找

传入要找的元素值 e，函数会从头到尾遍历顺序表，找到第一个和 e 相等的元素，就返回它的位序（从 1 开始数）；如果遍历完都没找到，就返回 0（代表查找失败）。

int LocateElem(SqList L, ElemType e) { for (int i = 0; i < L.length; i++) //从头到尾遍历顺序表的所有有效元素 if (L.data[i] == e) //找到和目标值e相等的元素 return i + 1; //下标为i的元素值等于e，返回其位序 i+1 return 0; //遍历完都没找到，返回0代表查找失败 }

最好情况：查找元素就在表头，只需要比较一次，时间复杂度为 O (1) 。

最坏情况：查找的元素在表尾或者表里根本没有这个元素，需要比较n次，时间复杂度为 O (n) 。

平均情况：

 ，每个元素被查找的概率相同，平均需要比较 (n+1)/2 次，平均时间复杂度为 O (n) 。

三. 顺序表的综合应用题

1. 从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删除元素的值，空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。

算法思想：首先对顺序表进行判空操作，空的话根本没法删，直接返回失败。然后要找最小值，就先把第一个元素当成初始最小值，同时记下它的位置，然后从头到尾遍历一遍表，遇到更小的就更新最小值和它的下标。找到之后，题目说空出来的位置用最后一个元素补，就可以直接把最后一个元素覆盖到最小值的位置。然后把表的长度减 1，最后把删掉的最小值通过引用参数带出去，返回成功。

bool Delete_Min(SqList &L, ElemType& x) //删除最小值，x用来带出被删的最小值，返回值代表是否删除成功 { if (L.length == 0) //顺序表判空 return false; x = L.data[0]; //初始化最小值为第一个元素，x先存下这个值 int pos = 0; //记录最小值的位置pos是0 for (int i = 1; i < L.length; i++) //从第二个元素开始遍历整个顺序表，找最小值 { if (L.data[i] < x) //如当前元素比记录的最小值小，更新最小值和它的位置 { x = L.data[i]; pos = i; } } L.data[pos] = L.data[L.length - 1]; //用最后一个元素填补最小值空出来的位置 L.length--; //顺序表长度减1 return true; //返回删除成功 } 

2. 设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为 O (1) 。

算法思想：这个题要求空间复杂度 O (1)，就是不能额外开新数组，只能在原表上改。所以使用二分法查找，只需要遍历半个顺序表就可以完成算法，定义 i 指向表的开头，然后交换左边i位置和其对称的右位置这两个位置的元素，交换完 i 往后走，直到i遍历半个顺序表，就全部交换完了。整个过程只需要一个临时变量存交换的值，空间就是 O (1)，而且只遍历一半的元素，时间也是 O (n)，特别高效。

bool Reverse(SqList& L) //原地逆置顺序表 { ElemType tmp; //定义临时变量，用来交换两个元素的值 for (int i = 0; i < L.length / 2; i++) //采用二分法，循环只需要走一半的长度 { tmp = L.data[i]; //把左边i位置元素和右边对称位置元素位置 L.data[i] = L.data[L.length - i - 1]; L.data[L.length - i - 1] = tmp; } return true; //返回删除成功 }

3. 对长度为n的顺序表L，编写一个时间复杂度为 O (n) 、空间复杂度为 O (1) 的算法，该算法删除顺序表中的所有值为x的元素。 

算法思想：第一种方法，使用快慢指针，快指针 i 遍历整个表，用慢指针 j 记录要保留的元素应该放的位置，只要 i 指向的元素不是 x，就把它放到 j 的位置，j 往后走。遍历完 j 就是剩下的元素个数，直接改表的长度就行。

bool Delete_x_1(SqList& L, ElemType x) //删除表中所有值为x的元素 { int j = 0; //慢指针k，记录保留元素的存放位置，初始是0 for (int i = 0; i < L.length; i++) //快指针i遍历整个顺序表 { if (L.data[i] != x) //如果当前元素不是x，说明要保留 { L.data[k] = L.data[i]; //把这个元素放到k的位置 k++; //k往后走，准备存下一个要保留的元素 } } L.length = j; //遍历完之后，k就是保留的元素个数，更新表的长度 return true; //返回删除成功 }

算法思想：第二种方法，统计要删除的元素个数 k，遍历的时候，遇到不是 x 的元素，就把它往前挪 k 个位置（因为前面有 k 个要删的元素，往前挪 k 刚好覆盖掉），最后更新表长度为总表长减 k 就行。

bool Delete_x_2(SqList& L, ElemType x) //删除表中所有值为x的元素 { int k = 0, i = 0; //k用来统计要删除的元素个数，i是遍历的指针 while (i < L.length) //循环遍历整个表 { if (L.data[i] == x) //如果当前元素是x，要删除的个数k加1 k++; else //不是x，就往前挪k个位置，覆盖掉要删的元素 L.data[i - k] = L.data[i]; i++; //遍历指针往后走 } L.length -= k; //表的长度减去删除的个数k，就是剩下的长度 return true; //返回删除成功 } 

4. 从顺序表中删除其值在给定s和t之间（包含 s 和 t ，要求s < t）的所有元素，若 s 或 t 不合理或顺序表为空，则显示出错信息并退出运行。

算法思想：这个题其实就是第 3 题的升级版，只是判断条件从 “等于 x” 变成了 “在 s 和 t 之间（包含）”。使用第 3 题的第二种思路，统计要删除的元素个数 k，遍历的时候，元素在 s 和 t 之间就 k 加 1，否则就往前挪 k 个位置，最后更新表的长度为总长度减 k 就行，返回成功。

bool Del_s_t(SqList& L, ElemType s, ElemType t) //删除表中值在[s,t]之间的元素，返回是否删除成功 { int k = 0; //k统计要删除的元素个数 if (L.length == 0 || s >= t) //合法性校验 return false; for (int i = 0; i < L.length; i++) //遍历整个顺序表 { if (L.data[i] >= s && L.data[i] <= t) //如果当前元素在[s,t]之间，要删除，k加1 k++; else //否则，把元素往前挪k个位置，覆盖要删除的元素 L.data[i - k] = L.data[i]; } L.length -= k; //更新表的长度，减去删除的个数 return true; //返回删除成功 }

5. 从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。

算法思想：题干中的有序顺序表提示我们，重复的元素肯定是挨在一起的。那我就用快慢指针，慢指针 i 指向已经保留的最后一个不重复元素，快指针 j 往后遍历。一开始 i 在0的位置，j 从1开始。如果 j 指向的元素和 i 的不一样，说明遇到了新的不重复元素，那 i 就往后走一位，同时把 j 的元素赋值到 i 的位置。j 遍历完之后，i+1 就是不重复元素的总个数，把表的长度改成 i+1 就行。

bool Delete_Same(SeqList& L) //有序顺序表去重，返回是否操作成功 { if (L.length == 0) //合法性校验 return false; //i是慢指针，指向最后一个不重复的元素，初始在0的位置 //j是快指针，遍历整个表，从1开始 for (int i = 0, j = 1; j < L.length; j++) if (L.data[i] != L.data[j]) //如果j的元素和i的不一样，说明是新的不重复元素 L.data[++i] = L.data[j]; //i先往后走一位，然后把j的元素赋值过来 L.length = i + 1; //遍历完之后，i+1就是不重复元素的个数，更新表的长度 return true; //返回操作成功 }

6. 将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。

算法思想：分别使用三个指针，i 指向 A 表的当前元素，j 指向 B 表的当前元素，k 指向结果表 C 要放元素的位置。然后循环比较 A[i] 和 B [j]，不断把更小的那个放到 C[k]，然后对应的指针往后走。等其中一个表遍历完了，就把另一个表剩下的元素直接全部接到 C 的后面就行。

bool Merge(SeqList A, SeqList B, SeqList& C) //把有序表A和B合并成有序表C，返回是否合并成功 { if (A.length + B.length > C.MaxSize) //先判断C的容量够不够装A和B的所有元素，不够直接返回false return false; int i = 0, j = 0, k = 0; //i遍历A表，j遍历B表，k记录C表的当前位置 while (i < A.length && j < B.length) //当A和B都还有元素没遍历完的时候 { if (A.data[i] <= B.data[j]) //比较A[i]和B[j]，把更小的放到C里 C.data[k++] = A.data[i++]; else C.data[k++] = B.data[j++]; } while (i < A.length) //如果A还有剩余，把A剩下的全部放进去 C.data[k++] = A.data[i++]; while (j < B.length) //如果B还有剩余，把B剩下的全部放进去 C.data[k++] = B.data[j++]; C.length = k; //更新C表的长度为k return true; //返回合并成功 }

7. 已知在一维数组A[m+n]中依次存放两个线性表(a1, a2, a3,···, am)和(b1, b2, b3,···,bn)。编写一个函数，将数组中两个顺序表的位置互换，即将(b1,b2,b3,···,bn)放在(a1, a2, a3,···, am)的前面。

算法思想：本题就是标准的三段逆置法啊，比如数组里是 [a1,a2,a3,b1,b2,b3]，要变成 [b1,b2,b3,a1,a2,a3]。方法是先把整个数组整体逆置，变成 [b3,b2,b1,a3,a2,a1]；再把b部分的前 n 个元素逆置，变成 [b1,b2,b3,a3,a2,a1]；最后把a部分的后 m 个元素逆置，变成 [b1,b2,b3,a1,a2,a3]，这样就原地逆置ok了。先写一个逆置函数操作，然后再写一个主函数，主函数调用三次这个函数就行。

typedef int DataType; //逆置数组A中，下标从left到right的元素 void Reverse(DataType A[], int left, int right, int arraySize) { if (left >= right || right >= arraySize) //合法性校验 return; int mid = (left + right) / 2; //找到区间的中点，循环到中点就停 for (int i = 0; i <= mid - left; i++) //交换区间两端的元素，往中间靠 { DataType tmp = A[left + i]; A[left + i] = A[right - i]; A[right - i] = tmp; } } void Exchange(DataType A[], int m, int n, int arraySize) //把数组A里的a表（前m个）和b表（后n个）互换位置，b放到前面 { Reverse(A, 0, m + n - 1, arraySize); //第一次逆置：把整个数组（a+b一共m+n个元素）整体逆置 Reverse(A, 0, n - 1, arraySize); //第二次逆置：把前n个元素（原来的b表）逆置，恢复原来的顺序 Reverse(A, n, m + n - 1, arraySize); //第三次逆置：把后面m个元素（原来的a表）逆置，恢复原来的顺序 }

8. 线性表(a1, a2, a3,···, am)中的元素递增有序且按顺序存储于计算机内。要求设计一个算法完成用最少时间在表中查找数值为x的元素，若找到，则将其与后继元素位置相交换，若找不到，则将其插入表中并使表中元素仍递增有序。

算法思想：题干都说用完成时间最少的算法了那肯定就是二分查找法，时间复杂度直接降到 O (log2n)。然后分两种情况处理：第一种，用二分成功找到 x 了，且只要 x 不是在表的最后一位，就把它和后面的相邻元素交换位置；第二种，没找到 x的话，二分结束的时候 low>high，此时 high 的下一个位置就是 x 应该插入的位置，我们把插入位置及后面的元素都往后挪一位，把 x 插进去，保证表还是递增有序的。

bool SearchExchangeInsert(ElemType arr[], ElemType x， int n) //有序数组arr（长度n）查找x，找到则和后继交换，找不到则插入保持有序 { int i = 0, low = 0, high = n - 1, mid; //i是插入时的循环变量，low、high是二分查找的左右边界，mid是二分中点 while (low <= high) //二分查找核心循环：只要左右边界没交叉，就继续找 { mid = (low + high) / 2; //计算当前区间的中点 if (arr[mid] == x) //找到x了，直接跳出循环，mid就是x的下标 break; else if (arr[mid] < x) //中点元素比x小，说明x在右半区间，更新左边界 low = mid + 1; else //中点元素比x大，说明x在左半区间，更新右边界 high = mid - 1; } if (arr[mid] == x && mid != n - 1) //情况1：找到x了，并且x不是最后一个元素 { int tmp = arr[mid]; //交换mid和mid+1位置的元素 arr[mid] = arr[mid + 1]; arr[mid + 1] = tmp; } if (low > high) //情况2：没找到x { for (i = n - 1; i > high; i--) //从最后一个元素开始，到high+1的位置，全部往后挪一位，腾出插入位置 arr[i + 1] = arr[i]; arr[i + 1] = x; //把x插入到high+1的位置，保证数组有序 } return true; }

9. 给定三个序列A、B、C，长度均为n，且均为无重复元素的递增序列，请设计一个时间上尽可能高效的算法，逐行输出同时存在于这三个序列中的所有元素。例如，数组A为{1, 2, 3}，数组B为{2, 3, 4}，数组C为{-1, 0, 2}，则输出2。

算法思想：这个题三个数组都是有序递增的，要找公共元素，使用三指针法，用三个指针 i、j、k，分别从 A、B、C 三个数组的开头出发，进入循环处理：第一种情况，如果三个指针指向的元素都相等，那这个就是我们要找的公共元素，输出之后三个指针都往后走一位；第二种情况，如果不相等，就先找到三个元素里最大的那个，然后把指向比最大值小的元素的指针往后移，因为数组是递增的，只有把小的元素指针往后移，才有可能找到等于最大值的元素，这样一次遍历就能走完，不用回头。

#define max(a, b) ((a > b) ? a : b) //求两个数的最大值 bool samekey(int A[], int B[], int C[], int n) //找三个有序数组A、B、C（长度都是n）的公共元素，逐行输出 { int i = 0, j = 0, k = 0; //三个指针i、j、k，分别指向A、B、C的当前元素，初始都在0的位置 while (i < n && j < n && k < n) //循环条件：三个指针都没走到数组末尾 { if (A[i] == B[j] && B[j] == C[k]) //情况1：三个元素都相等，是公共元素 { printf("%d\n", A[i]); //输出公共元素 i++; //三个指针都往后走一位 j++; k++; } else //情况2：元素不相等，移动指针 { int MaxNum = max(A[i], max(B[j], C[k])); //找到三个元素里的最大值 if (A[i] < MaxNum) //先找到三个元素里的最大值 i++; if (B[j] < MaxNum) j++; if (C[k] < MaxNum) k++; } } return true; }

10. 设将n(n>1)个整数存放到一维数组R中。设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0<p<n)个位置，即将R中的数据由(X0, X1,···, Xn-1)变换为(Xp, Xp+1,···, Xn-1, X0, X1,···, Xp-1)。

算法思想：又是三次逆置法，本地逆置不用额外开空间且主函数连续调用三次逆置函数时间也不会太拖沓。首先我们要明白，循环左移 p 位，本质就是把数组的前 p 个元素，整体搬到数组的最后面。比如数组是 [X0,X1,X2,X3,X4]，左移 2 位，要变成 [X2,X3,X4,X0,X1]，用三次逆置就能实现：（例子中的p=2）第一次，逆置前 p 个元素，变成 [X1,X0,X2,X3,X4]；第二次，逆置后面剩下的 n-p 个元素，变成 [X1,X0,X4,X3,X2]；第三次，逆置整个数组，变成 [X2,X3,X4,X0,X1]，刚好完成循环左移。注意三段逆置的顺序需根据题目不同而改变，就像本题和第7题一样都是三段逆置，但是主函数调用顺序并不同。

void Reverse(int R[], int from, int to) //逆置数组R中，下标从from到to的区间的元素 { for (int i = 0; i < (to - from + 1) / 2; i++) //采用二分法，循环只需要走区间的一半，走到中点就停 { int tmp = R[from + i]; //交换左边元素和右边对称的元素 R[from + i] = R[to - i]; R[to - i] = tmp; } } void Converse(int R[], int n, int p) //将长度为n的数组R，循环左移p位 { Reverse(R, 0, p - 1); //第一次逆置：逆置前p个元素 Reverse(R, p, n - 1); //第二次逆置：逆置后面n-p个元素 Reverse(R, 0, n - 1); //第三次逆置：逆置整个数组 }

11. 一个长度为L(L≥1)的升序序列S，处在第⌈L/2⌉个位置的数称为S的中位数，例如，若序列S=(11, 13, 15, 17, 19),则S的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数，例如，若S2=(2, 4, 6, 8, 20)，则S1和S2的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。

算法思想：使用二分法可以有效减少遍历时间。分别找两个序列当前区间的中位数，然后比较：

第一步：如果两个中位数相等，那这个数就是合并后的中位数，直接返回。

第二步：如果 A 的中位数小于 B 的，那最终的中位数肯定在 A 的后半段和 B 的前半段，可以忽略 A 的前半段和 B 的后半段。

第三步：如果 A 的中位数大于 B 的，那最终的中位数肯定在 A 的前半段和 B 的后半段，就可以忽略 A 的后半段和 B 的前半段。每次都把序列的长度缩小一半，直到两个序列都只剩一个元素，取较小的那个就是中位数。

int M_Search(int A[], int B[], int C[], int n) //找两个等长有序数组A、B（长度n）的中位数 { int Begin1 = 0， End1 = n - 1; //Begin1、End1是数组A当前区间的起点和终点，初始是整个数组 int Begin2 = 0， End2 = n - 2; //Begin2、End2是数组B当前区间的起点和终点，初始是整个数组（原代码bug修正：d2初始应为n-1，不是n-2） int mid1, mid2; //mid1是A当前区间的中位数下标，mid2是B的 while (Begin1 != End1 || Begin2 != End2) //mid1是A当前区间的中位数下标，mid2是B的 { mid1 = (Begin1 + End1) / 2; //计算两个数组当前区间的中位数下标 mid2 = (Begin2 + End2) / 2; if (A[mid1] == B[mid2]) //情况1：两个中位数相等，直接返回，就是最终的中位数 return A[mid1]; if (A[mid1] < B[mid2]) //情况2：A的中位数小于B的，舍弃A的前半段、B的后半段 { if ((Begin1 + End1) % 2 == 0) //如果区间长度是偶数，要保留中位数，所以起点设为m1 { Begin1 = mid1; ENd2 = mid2; } else //区间长度是奇数，中位数可以舍弃，起点设为mid1+1 { Begin1 = mid1 + 1; End2 = mid2; } } else //情况3：A的中位数大于B的，舍弃A的后半段、B的前半段 { if ((s1 + End2) % 2 == 0) //如果区间长度是偶数，保留中位数，终点设为mid1 { End1 = mid1; Begin2 = mid2; } else //区间长度是奇数，中位数可以舍弃，终点设为mid1 { End1 = mid1; Begin2 = mid2 + 1; } } } return A[Begin1] < B[Begin2] ? A[Begin1] : B[Begin2]; //循环结束，两个数组都只剩一个元素，返回较小的那个 }

12. 已知一个整数序列A=(a0,  a1,···, an-1)，其中0≤ai≤n(0≤i<n)。若存在ap1=ap2=...=apm=x且 m>n/2 (0≤p≤n, 1≤k≤m)，则称x为A的主元素。例如A=(0, 5, 5, 3, 5, 7, 5, 5)，则5为主元素;又如A=(0, 5, 5, 3, 5, 1, 5, 7)，则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1。

算法思想：由题意得，主元素的定义就是出现次数超过数组量的一半，所以它的出现次数，比其他所有元素的出现次数加起来还要多。

第一步：遍历一遍数组，找出候选主元素。首先把第一个元素当候选，计数设为 1，然后往后遍历：遇到和候选一样的元素，计数加 1；遇到不一样的，计数减 1；当计数变成 0 的时候，就把当前元素换成新的候选，计数重置为 1；

第二步：再遍历一遍数组，统计这个候选元素的出现次数，如果超过 n/2，就是主元素，返回它；否则就没有主元素，返回 - 1。

int Majority(int A[], int n) //找数组A（长度n）的主元素，存在则返回，否则返回-1 { int Host, count = 1, i; //Host是候选主元素，count是候选的计数，i是循环变量 Host = A[0]; //初始化候选主元素为第一个元素 for (i = 1; i < n; i++) //找候选主元素 { if (A[i] == Host) //当前元素和候选相同，计数加1 count++; else //当前元素和候选不同 { if (count > 0) //计数大于0，计数减1 count--; else //计数变成0，更换候选为当前元素，计数重置为1 { Host = A[i]; count = 1; } } } if (count > 0) //验证候选主元素的出现次数 for (i = count = 0; i < n; i++) //统计候选元素的出现次数 if (A[i] == Host) count++; if (count > n / 2) //如果出现次数超过n/2，返回候选主元素 return Host; else //否则没有主元素，返回-1 return -1; }

13. 给定一个含n(n≥1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5, 3, 2, 3}中未出现的最小正整数是1；数组{1, 2, 3}中未出现的最小正整数是4。

算法思想：由题意可以分析得到：长度为 n 的数组中未出现的最小正整数，一定在 1 到 n+1 之间。如果数组里 1 到 n 都有，那最小的就是 n+1；否则就是 1 到 n 里第一个没出现的数。

第一步：开一个长度为 n 的辅助数组，使用memset函数将该内存区域的初始值全设为 0；

第二步：遍历原数组，只要元素是 1 到 n 之间的正整数，就把辅助数组对应的位置由0设为1，标记这个数出现过；

第三步：遍历辅助数组，第一个值为 0 的位置，它的下标 + 1 就是我们要找的最小正整数；如果辅助数组全是 1，就返回 n+1。

int findMissMin(int arr[], int n) //找数组A（长度n）中未出现的最小正整数 { int i, * brr; //i是循环变量，B是辅助数组 brr = (int*)malloc(sizeof(int) * n); //申请长度为n的辅助数组，用来标记1~n的正整数是否出现 memset(B, 0, sizeof(int) * n); //把辅助数组的所有元素初始化为0 for(i = 0; i < n; i++) //第一次遍历：标记1~n的正整数是否出现 if (arr[i] > 0 && A[i] <= n) //只有元素是1~n之间的正整数，才需要标记 brr[arr[i] - 1] = 1; for (i = 0; i < n; i++) //第二次遍历：找第一个没出现的正整数 if (brr[i] == 0) //第一个值为0的位置，对应的正整数就是答案 break; return i + 1; //返回结果i+1就是最小未出现的正整数 }

14. 定义三元组(a, b, c)(a, b, c均为整数)的距离D=|a-b|+|b-c|+|c-a|。给定3个非空整数集合S1、S2和S3，按升序分别存储在3个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组(a,b,c)(a∈S1，b∈S2，c∈S3)中的最小距离。例如S1={-1, 0, 9}，S2={-25, -10, 10, 11}，S3={2, 9, 17, 30, 41}，则最小距离为2，相应的三元组为(9, 10, 9)。

算法思想：要找三元组的最小距离值，要让三个数尽可能接近。使用三指针法。

第一步：先定义三个指针 i、j、k，使其分别从三个数组的开头出发；

第二步：循环里先计算当前三个元素的距离，更新最小距离；

第三步：然后找到三个元素里最小的那个，把对应的指针往后移（同第9题逻辑），因为数组是递增的，只有把最小的数变大，才有可能让三个数更接近，距离更小；

第四步：直到有一个指针走到数组末尾，就结束循环，返回最小距离。

#define INT_MAX 0x7fffffff //int的最大值，用来初始化最小距离 int abs_(int a) //求绝对值 { if (a < 0) return -a; else return a; } bool xls_min(int a, int b, int c) //判断a是不是三个数里最小的 { if (a <= b && a <= c) return true; return false; } int FindMinofTrip(int A[], int n, int B[], int m, int C[], int p) //找三个有序数组A（长度n）、B（长度m）、C（长度p）的三元组最小距离 { int i = 0, j = 0, k = 0, D_min = INT_MAX, D; //i、j、k是三个数组的指针，初始在0的位置；D_min是最小距离，初始为最大值；D是当前距离 while (i < n && j < m && k < p && D_min>0) //循环条件：三个指针都没走到末尾，且当前最小距离大于0（距离最小是0，找到就可以提前结束） { D = abs_(A[i] - B[j]) + abs_(B[j] - C[k]) + abs_(C[k] - A[i]); //计算当前三个元素的距离 if (D < D_min) //如果当前距离更小，更新最小距离 D_min = D; if (xls_min(A[i], B[j], C[k])) //找到三个元素里最小的那个，把对应的指针往后移 i++; else if (xls_min(B[j], C[k], A[i])) j++; else k++; } return D_min; //返回最小距离 }