数据结构顺序表定义、操作与综合应用题解析

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

顺序表的缺点：

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

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

对于缺点的补充解析：

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

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

二。顺序表的基本操作

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.data == 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 = i; j < L.length; j++) //将第 i 个位置的元素前移
        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[j] = L.data[i]; //把这个元素放到 k 的位置
            j++; //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 - 1; //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;
            else //区间长度是奇数，中位数可以舍弃，起点设为 mid1+1
                Begin1 = mid1 + 1;
            End2 = mid2;
        }
        else //情况 3：A 的中位数大于 B 的，舍弃 A 的后半段、B 的前半段
        {
            if ((Begin1 + End2) % 2 == 0) //如果区间长度是偶数，保留中位数，终点设为 mid1
                End1 = mid1;
            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(brr, 0, sizeof(int) * n); //把辅助数组的所有元素初始化为 0
    for (i = 0; i < n; i++) //第一次遍历：标记 1~n 的正整数是否出现
        if (arr[i] > 0 && arr[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; //返回最小距离
}