Code59 零基础 · 顺序表 · 01—15

2026-09-14 · 零基础讲解 · 先读题目与条件，再看示例和逐步讲解

先读 第 0 课，再按每题“完整题干与条件 → 输入输出示例 → 人话讲解与状态推演 → 完整函数与逐句说明 → 自测”学习。题干整理和教学补充分别标注，原速查内容放在每题最后。

本篇对应全书第 01—15 题；章内编号与正式稿一致。题意为转述，例子和推导为本次补充；每题直接附完整函数；正式原稿只读。数组下标从 0 开始，n 为有效元素数；空间复杂度另行区分输出数组与工作空间。页码均为 Code59 原 PDF 页序，block 来自同书 source.json。

返回总目录

读代码前：编译环境与类型

本章展示的是完整函数，不是每题各有一个 main 的独立程序。练习编译一题时，将所需类型、辅助函数与题目函数放在同一份学习用 C 文件里，再添加调用它的 main；第 0 课给了最小程序例子。常用标准头文件如下（它们提供打印、分配空间、真假类型、整数上限）：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#define MAXSIZE 50

以下是本章使用的类型定义，不是要执行的解题步骤。字段含义见第 0 课；不要把不同章节重复的同名类型在同一文件中再定义多次。

/**/ #define MAXSIZE 50

typedef struct {
    int data[MAXSIZE];
    int length;
} SqList;

01｜有序顺序表插入 x（本章第 1 题）

题目与要求

题目（依据原题整理）：一个顺序表中的整数已经按从小到大的顺序排列。编写算法，把给定整数 x 插入表中，使插入后的顺序表仍然有序。

已知条件：输入顺序表 L 和整数 x；L.length 是现有元素个数，L.data 是存放元素的数组。

需要得到：在原表中完成插入，保留原有元素，表长增加 1。

输入 → 输出示例（教学补充）：L=[1,3,5]，x=4 → L=[1,3,4,5]，表长由 3 变为 4。

约定与提醒（教学补充）：这里允许相等的值，所谓“有序”是前一个数不大于后一个数；本函数把新值放在已有同值元素之后。数组必须还有空位，容量已满时返回失败且不修改原表。

题干回源：Code59 PDF 第 4 页；回源 · PDF 第 4 页 · b_4_3 。

1. 先把题目翻译成人话

顺序表就是“一排格子＋现在用了几格”。有序表示从左往右不会变小，例如 2、4、4、7。题目给你一个新数 x，要把它放进去，并且仍保持这个次序。它不是让你把整个表重新排序。

输入：[2,4,4,7]，x=3。输出：[2,3,4,4,7]，长度从 4 变 5。新数放在原下标 1 的位置，所以原来下标 1、2、3 的三个数都要向右挪一格。

2. 先用手指着格子做，暂时不看代码

步骤	做什么	格子 0、1、2、3、4 的内容
开始	有效长度是 4，最后一格是备用空间	2，4，4，7，空
找位置	3 不小于 2，但小于第一个 4；确定 pos=1	不修改数组
i=3	把原末尾 7 从下标 3 复制到 4	2，4，4，7，7
i=2	把下标 2 的 4 复制到 3	2，4，4，4，7
i=1	把下标 1 的 4 复制到 2	2，4，4，4，7
填新数	把下标 1 改成 3	2，3，4，4，7
收尾	长度改为 5	五个格子都有效

中间出现两个 7 没关系：我们是在复制和覆盖，尚未完成时不要求每一步都是最终答案。用到的变量：i 是手指目前指的下标，pos 是新数应放的位置，x 是新数本身。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

int findInsertPos(SqList L, int x) {
    for (int i = 0; i < L.length; i++) {
        if (x < L.data[i])
            return i;
    }
    return L.length;
}

bool insertOrdered(SqList *L, int x) {
    if (L->length >= MAXSIZE)
        return false;

    int pos = findInsertPos(*L, x);
    for (int i = L->length - 1; i >= pos; i--)
        L->data[i + 1] = L->data[i];

    L->data[pos] = x;
    L->length++;
    return true;
}

先读第一个函数。int 表示交回一个整数位置；参数 SqList L 是要检查的表，int x 是新数。for 让 i 从 0 每次加 1，一直到长度之外才停止。if(x<L.data[i]) 是问“这里的旧数是不是已经比 x 大了？”第一次成立就 return i，位置已经找到，不必继续。若全部旧数都不比 x 大，末尾的 return L.length 表示追加到最后。

再读第二个函数。它收到表的地址 SqList *L，因为要改原表；L->length 是沿地址取得长度。先判断容量，满了就返回 false，后面一行也不做。findInsertPos(*L,x) 中 *L 取出表本身，交给只负责找位置的函数，返回结果存入 pos。

移动循环的初始化是 length-1，也就是原末元素；条件 i>=pos 把插入位置本身也包括；每轮 i-- 向左走。data[i+1]=data[i] 是把当前位置复制到右邻格。循环结束才写 x，再用 length++ 承认新增元素，return true 告诉调用者成功。

4. 为什么不能从左往右搬？自己试一下

若 [2,4,6,7] 从下标 1 开始正向搬，先把 4 写到下标 2，就覆盖了尚未保存的 6；下一轮读到的已不是 6，而是 4。这不是方向随便选的问题，是会丢原数。

练习：向 [2,4] 插入 1，pos 是几，要搬几次？答案：pos=0，先搬下标 1 的 4，再搬下标 0 的 2，共两次；填 1 后为 [1,2,4]。x=9 则 pos=2，搬移循环一次不执行。

学懂后回看：结论、复杂度与回源

题意与结论：原表已经按非递减次序排列，插入一个 x 后还要有序。找到第一个大于 x 的元素，把它及后面的元素右移，再填入 x。

思路推导：不必“加在末尾再全排序”。原表已经有序，新元素只缺一个位置。找到插入位置 pos 后，问题就变成给它腾一个空格。为什么从后往前移？因为正向移动会覆盖尚未搬走的数据。

走一遍：[2,4,4,7] 插入 4。扫描时跳过 2,4,4，得到 pos=3。把下标 3 的 7 放到下标 4，再令 data[3]=4，长度从 4 改为 5，得到 [2,4,4,4,7]。若插入 1，要依次搬 7、4、4、2；若插入 9，不搬动，直接接到末尾。

代码抓手与正确性：findInsertPos 返回的是数组下标，不是第几号元素。移动循环从 length-1 递减到 pos，执行 data[i+1]=data[i]；最后写 data[pos]=x、length++。插入点左侧都不大于 x，右侧都大于 x，所以有序性保持。

复杂度与易错点：最坏时间 O(n)，工作空间 O(1)。二分找位置只能减少比较，不能消除顺序表搬移的 O(n)。空表可插；表满须返回失败。这里允许相等元素，若题目禁止重复，应另外判断，不能擅自改题。

回源：PDF 第 4 页；回源 · PDF 第 4 页 · b_4_3 。正式代码

02｜用尾元素覆盖第一个最小值（本章第 2 题）

题目与要求

题目（依据原题整理）：在顺序表中找出最小元素；如果最小值出现多次，选择第一次出现的那个。用表的最后一个元素覆盖选中的位置，并交回覆盖前的最小值。若选中的位置就是表尾，则不改变顺序表。

已知条件：输入一个非空顺序表，元素不要求有序。

需要得到：修改后的顺序表，以及原最小值；按本题“覆盖”的口径，表长不变。

输入 → 输出示例（教学补充）：[6,2,5,2,9] → 表变为 [6,9,5,2,9]，交回 2。输入 [5,3,1] → 表不变，交回 1。

约定与提醒（教学补充）：原资料代码把“覆盖”和“删除”的处理混在一起；锁定校订稿按题面采用覆盖，不能额外减小表长。下面函数的 true/false 只表示成功与否，最小值通过输出参数 minValue 交回；空表返回失败。

题干回源：Code59 PDF 第 4 页；回源 · PDF 第 4 页 · b_4_1 。原稿歧义及校订解释见本题末尾。

1. 先弄清“覆盖”不是“删除”

输入 [6,2,5,2,9]，要找最小值第一次出现的位置，用末元素盖掉它，同时告诉调用者原最小值是多少。输出表是 [6,9,5,2,9]，交回最小值 2，长度仍为 5。它不要求保持次序，也不要求去掉尾部那个 9。

pos 存位置，*minValue 存目前见过的最小数。两者不是同一件事：最小数 2 的位置是下标 1。

2. 每次读一个数，更新两本小账

读到哪里	读到的数	是否比目前的最小值更小	minValue、pos
先看下标 0	6	用它初始化	6、0
i=1	2	2<6，更新	2、1
i=2	5	5<2 不成立	2、1
i=3	2	2<2 不成立	2、1
i=4	9	9<2 不成立	2、1
扫完	末数是 9	用它覆盖下标 1	返回值仍为 2

为什么最开始不用 0 当最小值？本表全是正数，如果一开始记 0，以后没有一个数更小，答案会错。先取一个真的存在的元素最稳妥。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

bool coverFirstMinWithLast(SqList *L, int *minValue) {
    if (L == NULL || minValue == NULL || L->length <= 0)
        return false;

    int pos = 0;
    *minValue = L->data[0];

    for (int i = 1; i < L->length; i++) {
        if (L->data[i] < *minValue) {
            *minValue = L->data[i];
            pos = i;
        }
    }

    if (pos != L->length - 1)
        L->data[pos] = L->data[L->length - 1];

    return true;
}

第一条 if 的三个条件用“或者”连接：表地址无效、接收最小值的地址无效、表为空，有任何一种就不能做，返回 false。通过检查后才能读 data[0]。int pos=0 记首位置，*minValue=data[0] 把首值写到调用者给的格子。

for 从 i=1 开始，因为第 0 个已经用于初始化。if 严格更小才进入花括号，同时改最小值和位置。若最小位置不是 length-1，才做覆盖；否则它就在末尾，无须动。最后 true 只是成功标志，不是最小数；最小数通过 *minValue 写出。

例如调用者可有整数 answer，把 &answer 传入；调用成功后 answer 变成 2。星号不是乘法，是访问那个接收答案的格子。

4. 改错一处会怎样？自己试一下

把 < 改成 <=，第二个 2 会覆盖 pos 的记录，结果选到最后一次出现而非第一次。把末尾加上 length--，又会从覆盖题变成删除题。

练习：[5,3,1] 会怎样？答案：pos=2 正好是末尾，不改表，输出参数写入 1，返回 true。

学懂后回看：结论、复杂度与回源

题意与结论：找最小值；若出现多次，选第一次；用最后一个元素覆盖它，并返回原最小值。注意题目说的是“覆盖”，不是“删除”。

思路推导：无序表没有可利用的大小顺序，必须检查所有元素。用 pos 记目前最小值的位置；只有发现严格更小的值才更新，遇到相等值不更新，就能保留首次位置。

走一遍：[6,2,5,2,9]。初始最小位置 0；读到第一个 2 后改为 1；后面的 5、2、9 都不使它更新。先保存返回值 2，再用尾元素 9 覆盖下标 1，得到 [6,9,5,2,9]，长度仍为 5。若为 [6,3,1]，最小值就在末尾，自己覆盖自己，表不变。

代码抓手与正确性：循环不变量是“pos 指向已扫描部分中第一次出现的最小值”。比较用 <，不能写 <=；最小值在扫描中保存在输出参数里，覆盖不会丢失返回值。返回的布尔值表示操作成功与否，最小值通过 *minValue 带回。

复杂度与易错点：时间 O(n)，空间 O(1)；空表返回失败，单元素表不变。覆盖通常会破坏原来的次序。考试若另问“删除最小值”，可尾元素补位后 length--；但这一句在本题不能加。

回源：PDF 第 4 页；回源 · PDF 第 4 页 · b_4_1；PDF 第 4 页 · b_4_6；PDF 第 4 页 · b_4_8 。正式代码

03｜循环左移 p 个位置（本章第 3 题，2010）

题目与要求

题目（依据原题整理）：将 n 个整数存放在数组 R 中，设计尽可能高效的算法，把序列循环左移 p 个位置。也就是把 (X0,…,Xn-1) 变为 (Xp,…,Xn-1,X0,…,Xp-1)。

已知条件：输入数组 R、元素个数 n 和移动量 p；本题范围为 0<p<n。

需要得到：直接改好原数组，元素既不丢失也不新增，前 p 个元素按原顺序搬到末尾。

输入 → 输出示例（教学补充）：R=[1,2,3,4,5]，p=2 → [3,4,5,1,2]。

约定与提醒（教学补充）：左移不是把左边的数删掉，也不是将空位填 0。下面采用原地算法，不另建一个同样大的数组；超出题设的移动量不由本函数自动归一化。

题干回源：Code59 PDF 第 4 页；回源 · PDF 第 4 页 · b_4_2 。

1. “循环左移”到底把谁放哪里？

输入 [1,2,3,4,5]，p=2。左边两个数不是删除，而是搬到末尾，输出 [3,4,5,1,2]。“循环”强调从一端出去的数回到另一端。p 是移动几个位置，n=5 是总元素数。

先分组：A 段是 [1,2]，B 段是 [3,4,5]。要求是交换两段的前后次序，但不改变段内部的先后。

2. 把“大动作”拆成三次首尾交换

操作	交换哪些格子	操作后
逆置全体 0..4	1 与 5 交换，2 与 4 交换	[5,4,3,2,1]
逆置前 n-p=3 个，即 0..2	5 与 3 交换	[3,4,5,2,1]
逆置后 p=2 个，即 3..4	2 与 1 交换	[3,4,5,1,2]

“逆置”是把一段次序翻转。第一次已经让 B 段跑到 A 前面，但两段内部都反了；后两次分别把内部顺序恢复。这就是三次操作的理由。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

void reverseRange(int R[], int start, int end) {
    for (int i = start, j = end; i < j; i++, j--) {
        int temp = R[i];
        R[i] = R[j];
        R[j] = temp;
    }
}

void rotateLeft(int R[], int n, int p) {
    reverseRange(R, 0, n - 1);
    reverseRange(R, 0, n - p - 1);
    reverseRange(R, n - p, n - 1);
}

reverseRange 只管翻转 start 到 end，两个端点都包括。i 从左端出发，j 从右端出发，只有 i<j 才需要交换。i、j 相等时是中间那个数，不必和自己换。

交换三句不能压成两句：temp=R[i] 先寄存左值；R[i]=R[j] 把右值写过来；R[j]=temp 把寄存的旧左值放回右侧。否则先覆盖左值后就再也找不到它。每轮末尾 i++、j--，两只手向内移动。

rotateLeft 没有循环，它调用三次小任务：全区间 [0,n-1]；前段 [0,n-p-1]；后段 [n-p,n-1]。注意它此时切的是“整体已经翻转之后”的两段，因此前段长度是 n-p，不是 p。

4. 自己试一下，并检查是否真懂了

练习：[a,b,c,d] 左移 1。三次状态依次为 [d,c,b,a]、[b,c,d,a]、[b,c,d,a]；最后一段只有 a，逆置它不改变任何东西。最终不是 [d,a,b,c]，后者是右移 1。

三遍扫描总工作仍与 n 成正比，不是 n³；本题 0<p<n，先掌握这个题设，再考虑任意 p 的取模扩展。

学懂后回看：结论、复杂度与回源

题意与结论：把开头 p 个元素整体移到末尾，各段内部次序不变。把数组写成 AB，目标就是 BA，用三次逆置原地完成。

思路推导：每次左移一格要搬 n 个元素，做 p 次是 O(np)。三次逆置利用 (AB)ᴿ=BᴿAᴿ：先逆置整体，再分别逆置目前的前 n-p 个和后 p 个，就得到 BA。

走一遍：[1,2,3,4,5,6,7]，p=2。整体逆置成 [7,6,5,4,3,2,1]；逆置前 5 个变成 [3,4,5,6,7,2,1]；逆置后 2 个得到 [3,4,5,6,7,1,2]。

代码抓手与正确性：reverseRange(R,start,end) 使用闭区间，两端交换后同时向内走。三个区间为 [0,n-1]、[0,n-p-1]、[n-p,n-1]。逆置只改变位置、不丢元素，两段在第二、三次逆置后分别恢复内部顺序。

复杂度与易错点：时间 O(n)，空间 O(1)。另一套等价写法是先逆置原前 p 个、原后 n-p 个，再逆置整体；不要混用两套区间。题设 0<p<n；通用程序若允许任意 p，需先处理空数组及取模，这属于工程扩展。

回源：PDF 第 4 页；回源 · PDF 第 4 页 · b_4_2；PDF 第 4 页 · b_4_7 。正式代码

04｜无序顺序表去重，保留首次（本章第 4 题）

题目与要求

题目（依据原题整理）：从一个顺序表中删除所有重复出现的元素，每种值只保留第一次出现的那一个，并更新表长。设计相应算法。

已知条件：输入顺序表 L，不能假定元素已经排好序，相同值可能分散在不同位置。

需要得到：去重后的有效元素序列；保留下来的元素仍按原来首次出现的先后顺序排列。

输入 → 输出示例（教学补充）：[3,1,3,2,1] → [3,1,2]，表长由 5 变为 3。

约定与提醒（教学补充）：“去重”不是把所有曾经重复过的值全部删光，也不是先排序。缩短表长以后，数组旧尾部即使仍有数据，也不属于有效顺序表。这里讲解锁定稿的常量辅助空间实现。

题干回源：Code59 PDF 第 5 页；回源 · PDF 第 5 页 · b_5_0；PDF 第 5 页 · b_5_1 。

1. 去重后保留的是“第一次遇到的那个”

输入 [3,1,3,2,1]，输出 [3,1,2]。表没有排好序，相同值可能隔很远；不能排序成 [1,2,3] 后说完成，因为首次出现次序变了。

i 指本轮要留下的一个值；j 向后读；k 指下一个允许写的位置。先把所有后续 3 清掉，再清掉后续 1，不会把当前保留值一起删掉。

2. 第一轮详细到每一次写入

本轮固定 i=0，值为 3	比较	动作	k 的变化
开始	保留 data[0]	k=1，从它后面开始填	1
j=1，读到 1	1!=3	data[1]=1	1→2
j=2，读到 3	3!=3 为假	不写，跳过重复	仍 2
j=3，读到 2	2!=3	data[2]=2	2→3
j=4，读到 1	1!=3	data[3]=1	3→4
结束	新有效区为 0..3	length=4	[3,1,2,1]

第二轮 i=1 保留 1，k=2：读 j=2 的 2，写入并让 k=3；读 j=3 的 1，跳过；长度变 3。最后 i=2 保留 2，它后面已没人，结束。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

void uniqueUnordered(SqList *L) {
    for (int i = 0; i < L->length; i++) {
        int k = i + 1;
        for (int j = i + 1; j < L->length; j++) {
            if (L->data[j] != L->data[i])
                L->data[k++] = L->data[j];
        }
        L->length = k;
    }
}

外层 for 每轮选定 data[i]。k=i+1 留住它及之前的内容，只重排后缀。内层 j 也从 i+1 开始，逐个看后面的数。if 用不等号，因为我们要复制“可以留下的数”，不是复制要删的重复值。

L->data[k++]=L->data[j] 先写当前 k，再 k 加一；跳过重复时 k 不加。因此 k 落后于或等于 j，写入不会覆盖后面还没读到的格子。一轮全读完才 length=k，下一轮只看新的有效长度。

4. 自己试：旧尾部是否一定要清零？

不需要。最终内存尾部可能仍有旧数，但 length=3 时只承认前三格。练习 [2,2,2]：第一轮两个后续 2 都不写，k 保持 1，length=1，外层下一次 i=1 已不小于长度，结束，结果 [2]。

这是一种省空间的重复扫描法；不要见到两个 for 就说它高效到 O(n)，它最坏确实要平方量级比较。

学懂后回看：结论、复杂度与回源

题意与结论：去掉后面重复出现的值，保留第一次出现的次序。正式代码对每个保留值扫描剩余后缀，把不等于它的元素向前压紧。

思路推导：无序时，相同值未必挨在一起。若直接排序再去重，会改变首次出现顺序。这里宁可多做比较，也不额外开集合或改变保留元素的相对顺序。

走一遍：[3,1,3,2,1]。第一轮固定 3，保留后缀中不为 3 的 1,2,1，得到有效表 [3,1,2,1]。第二轮固定 1，后缀只保留 2，变为 [3,1,2]。第三轮无需再删除，完成。

代码抓手与正确性：外层 i 是本轮保留值的位置；j 向后读取；k=i+1 表示下一个可写位置。遇到 data[j]!=data[i] 才执行 data[k++]=data[j]；一轮末尾把长度改为 k。写位置不超过读位置，因此不会毁掉尚未读取的元素。每轮清理一种值的后续副本，最终每种值只留首次。

复杂度与易错点：最坏时间 O(n²)、空间 O(1)，两层循环不是线性。长度缩短后，旧尾部数据即使还在内存中，也不再属于表。哈希集合可在合适假设下做到期望 O(n)，但需额外空间；那是补充方案，不是正式代码正在做的事。

回源：PDF 第 5 页；回源 · PDF 第 5 页 · b_5_0；PDF 第 5 页 · b_5_1；PDF 第 5 页 · b_5_5 。正式代码

05｜有序顺序表去重（本章第 5 题）

题目与要求

题目（依据原题整理）：给定一个有序顺序表，设计尽可能高效的算法，删除重复元素；每种值只保留第一次出现的一个，并更新表长。

已知条件：表内元素按非递减顺序排列，即前一个数不大于后一个数，因此相等元素连续出现。

需要得到：仍然有序、每种值只出现一次的顺序表。

输入 → 输出示例（教学补充）：[1,1,2,2,2,4] → [1,2,4]，新表长为 3。

约定与提醒（教学补充）：输入“已经有序”是本题与第 4 题的关键区别；不能把这里的相邻判重办法直接用于 [1,2,1]。空表保持为空表。

题干回源：Code59 PDF 第 5 页；回源 · PDF 第 5 页 · b_5_2 。

1. 和上一题只差“有序”，为什么能快这么多？

有序表里同一个值必然聚在一起：[1,1,2,2,2,4]。保留每一团的第一个即可，不用回头到全表找。输出 [1,2,4]。

k 不是“当前读取位置”，而是“已经留下几个数”，也正好等于下一次写入下标；j 才是读位置。首个数先留下，所以 k 从 1 开始。

2. 把 j 和 k 分开记

j、读到的数	最后保留值 data[k-1]	是否写入	执行后 k、有效前缀
开始	1	首元素预先保留	1，[1]
1，1	1	相同，不写	1，[1]
2，2	1	写 data[1]=2	2，[1,2]
3，2	2	相同，不写	2，[1,2]
4，2	2	相同，不写	2，[1,2]
5，4	2	写 data[2]=4	3，[1,2,4]

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

void uniqueOrdered(SqList *L) {
    if (L->length <= 1)
        return;

    int k = 1;
    for (int j = 1; j < L->length; j++) {
        if (L->data[j] != L->data[k - 1])
            L->data[k++] = L->data[j];
    }
    L->length = k;
}

第一条 if 处理长度 0 或 1：没有重复可删，直接结束 void 函数。k=1 是承认第一个数已经留下。j 从 1 读第二个数，直到原有效长度之外。

data[j]!=data[k-1] 的 k-1 是最后一次真的保留下来的位置。不同则复制到 data[k]，并 k++；相同则什么也不写，但 j 仍按 for 前进。最后 length=k 把新表长度设置成保留数的个数。

4. 你可能会误写的地方

若把 k++ 放到 if 外面，读到重复也会给保留区增加一个位置，重复就没有真正被跳过。若拿这个方法处理 [1,2,1]，最后一个 1 不等于前面保留的 2，会被留下；所以“有序”不是装饰条件。

练习 [5,5,7]：最终 k=2，结果 [5,7]。每个 j 只读一次，即使总共写了两次，也仍是线性工作量。

学懂后回看：结论、复杂度与回源

题意与结论：有序表的相同元素连续出现，因此只需保留每个连续段的第一个元素，用读写双指针一次完成。

思路推导：上一题要到整个后缀找重复，本题的有序性消除了这种需要。j 负责读原表，k 既是已保留元素数，也是下一次写入的位置。

走一遍：[1,1,2,2,2,4]。先保留第一个 1，k=1；第二个 1 与最后保留值相同，跳过；遇 2 写到下标 1，k=2；再遇两个 2 都跳过；遇 4 写到下标 2，k=3。最终有效表为 [1,2,4]。

代码抓手与正确性：比较对象是 data[k-1]，即“最后已经保留的值”；不是含糊地比较某个被覆盖过的旧位置。循环后 data[0..k-1] 恰好是已读前缀的去重结果，故把 length=k 即可。

复杂度与易错点：时间 O(n)，空间 O(1)。空表要先返回，否则把 k 初始化为 1 会制造一个不存在的元素。全相同最终长度为 1；无重复则长度不变。本题并不要求把无效尾部清零。

回源：PDF 第 5 页；回源 · PDF 第 5 页 · b_5_2；PDF 第 5 页 · b_5_3；PDF 第 5 页 · b_5_6 。正式代码

06｜有序表众数及出现次数（本章第 6 题）

题目与要求

题目（依据原题整理）：在有序顺序表中找出出现次数最多的元素，并给出它出现了多少次。如果有多个元素并列最多，选数值最小的那个。要求算法尽可能高效。

已知条件：输入按非递减顺序排列的非空顺序表；相同值可以重复出现。

需要得到：两个结果——选中的元素值和它的出现次数，不能只返回次数。

输入 → 输出示例（教学补充）：[1,1,2,2,3] → 元素 1，次数 2；1 和 2 并列时取较小值 1。

约定与提醒（教学补充）：本题找“最多”，不要求次数超过一半。所有元素只出现一次时，答案是最小元素、次数 1；空表没有众数，函数返回失败。

题干回源：Code59 PDF 第 5 页；回源 · PDF 第 5 页 · b_5_10 。

1. 众数是一种“出现最多的值”

输入 [1,1,2,2,3,3,3]，输出值 3、次数 3。次数相同则要较小值。它不问最大元素，也不问所有元素之和。

count 是当前这一团相同值有几个；maxCount 是目前纪录中的最高次数；maxValue 是创造该纪录的值。maxValue 这个名字容易误导，它是“频次冠军的值”，不是数组最大值。

2. 分清“正在数”与“已经结算”

当前动作	count	纪录 maxValue、maxCount
首元素 1 初始化	1	1、1
再读一个 1	2	暂不改纪录，先继续数
遇到 2，上一团 1 结束	先结算 2，再重置 1	1、2
再遇 2	2	1、2
遇 3，上一团 2 结束	与纪录打平，不换冠军；重置 1	1、2
再读两个 3	3	暂仍为 1、2
数组结束，手动结算末团	3 超过 2	3、3

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

bool modeOfOrderedList(SqList L, int *mode, int *frequency) {
    if (L.length <= 0 || mode == NULL || frequency == NULL)
        return false;

    int maxValue = L.data[0];
    int maxCount = 1;
    int count = 1;

    for (int i = 1; i < L.length; i++) {
        if (L.data[i] == L.data[i - 1]) {
            count++;
        } else {
            if (count > maxCount) {
                maxCount = count;
                maxValue = L.data[i - 1];
            }
            count = 1;
        }
    }

    if (count > maxCount) {
        maxCount = count;
        maxValue = L.data[L.length - 1];
    }

    *mode = maxValue;
    *frequency = maxCount;
    return true;
}

先检查空表与两个输出地址。三个初始化分别表示：暂把首值当冠军、冠军次数为 1、当前段也数到 1。for 从第二个元素开始，与紧挨前一个 data[i-1] 比较。

相等就 count++；不等进入 else，说明上一段结束了。如果 count 严格超过 maxCount，就同时更新冠军次数与冠军值。这里冠军值取 data[i-1]，因为 i 已经是下一段的新值；然后 count=1 把新段的第一个数算上，不能重置为 0。

for 外面又有一个 if，专门补结算最后一段。末尾 *mode=maxValue、*frequency=maxCount 把两个答案写到调用者给的格子，再返回成功标志。

4. 自己试，必须解释为什么

输入 [4,4,6,6] 的答案是 4、2；最后一段与纪录相等，不替换。输入 [7,7,7] 时，中途从不进入“换值”分支，如果删去循环后的 if，就错报次数为 1；保留收尾才能得到 7、3。

学懂后回看：结论、复杂度与回源

题意与结论：找频次最大值；频次并列时取数值较小者。有序使每种值形成连续段，只需统计段长，维护目前最长段。

思路推导：count 统计正在扫描的段；maxCount 和 maxValue 记录目前最优次数与对应值（初始化为首元素出现一次）。遇到新值时，上一段才正式结束。只有新段次数严格大于最优次数才更新，并列不更新就留下较小值。

走一遍：[1,1,2,2,3,3,3]。读到第一个 2，结算 1 的次数 2；读到第一个 3，结算 2 的次数也为 2，并列时仍保留 1；数组读完后结算最后的 3 段，次数 3，结果改为 (3,3)。若数组只有 [1,1,2,2]，结果为 (1,2)。

代码抓手与正确性：初始当前次数和最优次数均为 1，最优值为首元素。循环内只在“值改变”时结算旧段；循环结束还必须再结算一次。这个收尾对应最后一段没有后继新值来触发结算。

复杂度与易错点：时间 O(n)，空间 O(1)。空表操作失败。原稿存在未初始化问题，锁定校订版已修。众数只要求次数最多，不保证超过总数一半；不要与下一题主元素混淆。

回源：PDF 第 5 页；回源 · PDF 第 5 页 · b_5_10；PDF 第 5 页 · b_5_4；PDF 第 5 页 · b_5_9 。正式代码

07｜主元素：次数严格过半（本章第 7 题，2013）

题目与要求

题目（依据原题整理）：已知整数数组 A 有 n 个元素。若某个值的出现次数严格超过 n/2，称它为主元素。设计尽可能高效的算法，存在主元素时返回该值，否则返回 -1。

已知条件：n>0，各元素满足 0<=A[i]<n；数组不要求有序。

需要得到：一个主元素值或表示不存在的 -1，原数组无需重排。

输入 → 输出示例（教学补充）：[0,2,2,1,2] → 2，因为出现 3 次，超过 5/2；[0,1,1,0] → -1，因为两种值都只占一半。

约定与提醒（教学补充）：出现次数最多不一定是主元素；“严格超过”不能写成“大于等于”。值域限制是下面计数数组能安全使用的前提，不能悄悄换成任意整数。

题干回源：Code59 PDF 第 6 页；回源 · PDF 第 6 页 · b_6_1；PDF 第 6 页 · b_6_0 。

1. “超过一半”和“出现最多”不是同一句话

主元素必须占严格多数。五个元素里至少出现 3 次才够，六个元素里至少出现 4 次才够。输入 [0,2,2,1,2] 输出 2；输入 [0,0,1,1] 输出 -1（不存在）。

题设每个值都在 0 到 n-1，可给每个可能的值分配一个计数格。count[2] 记录“数字 2 出现了几次”，不是“下标 2 上的数字”。

2. 把数字当作计数格的门牌

i	A[i]	这次改哪个格子	count[0..4]
初始	—	calloc 清零	[0,0,0,0,0]
0	0	count[0] 加一	[1,0,0,0,0]
1	2	count[2] 加一	[1,0,1,0,0]
2	2	count[2] 加一	[1,0,2,0,0]
3	1	count[1] 加一	[1,1,2,0,0]
4	2	count[2] 加一	[1,1,3,0,0]

再看每个计数格：只有 count[2]=3 大于整数除法 5/2=2，所以候选值 2 合格。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

int majorityElement(int A[], int n) {
    int *count = (int *)calloc(n, sizeof(int));
    if (count == NULL)
        return -1;

    for (int i = 0; i < n; i++)
        count[A[i]]++;

    int result = -1;
    for (int value = 0; value < n; value++) {
        if (count[value] > n / 2) {
            result = value;
            break;
        }
    }

    free(count);
    return result;
}

calloc(n,sizeof(int)) 为 n 种可能值准备 n 个计数格，初始都为 0；count==NULL 是没申请到空间，提前退出。第一个 for 中 count[A[i]]++ 要从内往外读：先读 A[i] 得到一个数字，再以这个数字为下标去增加对应次数。

result=-1 先把答案设为不存在。第二个 for 的 value 枚举“可能的数值”，与前一循环枚举“输入位置”的 i 不同；某计数严格超过半数，就 result=value、break 停止寻找。free(count) 归还临时计数空间后，return 的是已经存进 result 的整数，不再读取被释放数组。

4. 自己试：两个最容易错的替换

写成 count[i]++ 会让每个位置都只加一次，完全没统计相同值；写成 >=n/2 会把恰好一半也算入。练习 n=6，[1,1,1,2,2,3]：1 虽然最多，也只有 3 次，不严格大于 3，答案 -1。

先掌握这份桶计数代码；学完后若想省数组空间，再读下方投票法补充，不要把两种变量的含义混在一起。

学懂后回看：结论、复杂度与回源

题意与结论：在 0<=A[i]<n 的条件下，找出现次数严格大于 n/2 的值，不存在则返回 -1。正式代码使用计数桶，不是摩尔投票法。

思路推导：逐个候选再扫描全数组计数是 O(n²)。值域已知，可令 count[x] 直接记录值 x 的次数，避免重复扫描。出现一次就加一，某桶超过半数即可确认主元素。

走一遍：[0,2,2,1,2]，n=5。读完各桶为 count[0]=1、count[1]=1、count[2]=3，因为 3>5/2，主元素是 2。[1,1,2,2] 中两个值都只出现 2 次，2 并不大于 4/2，所以没有主元素。

代码抓手与正确性：桶必须清零；桶下标用元素值，不是元素位置；判断用 >，不能用 >=。若两种不同值都过半，总次数会超过 n，所以主元素至多一个。

补充优化：若还要求 O(1) 空间，可用“不同值成对抵消”的投票法：计数为 0 时换候选，相同加一、不同减一；最后必须重新计数验证候选。抵消只保证“若有主元素，它不会被完全抵消”，不保证一定有主元素。

复杂度与易错点：正式桶法时间 O(n)、空间 O(n)，含桶初始化；投票法两趟仍为 O(n)、空间 O(1)。桶法依赖题设值域，不能拿任意整数直接当下标。实际程序还要区分内存分配失败与数学上不存在主元素。

回源：PDF 第 6 页；回源 · PDF 第 6 页 · b_6_1；PDF 第 6 页 · b_6_0；PDF 第 6 页 · b_6_5 。正式代码

08｜最小缺失正整数（本章第 8 题，2018）

题目与要求

题目（依据原题整理）：给定一个含 n 个整数的数组，设计时间上尽可能高效的算法，找出没有在数组中出现过的最小正整数。

已知条件：数组可以无序，可以有重复值，也可以包含负数和 0。

需要得到：一个大于 0 且未出现过的最小整数，不是数组中现有的最小正数。

输入 → 输出示例（教学补充）：[-5,3,2,3] → 1；[1,2,3] → 4；[3,4,-1,1] → 2。

约定与提醒（教学补充）：0 不是正整数。下面的实现允许使用辅助标记数组；辅助空间的申请及释放见代码，额外空间不是常量。若扩展到空数组，答案为 1。

题干回源：Code59 PDF 第 6 页；回源 · PDF 第 6 页 · b_6_2 。

1. 先用小数据理解“最小缺失正整数”

正整数从 1 开始，负数和 0 不算。输入 [3,4,-1,1]：1 出现了，2 没出现，所以答案就是 2，无须继续关心 5、6、7。

seen[x] 是一张签到表：“正整数 x 来过吗？”布尔值 true 表示来过，false 表示没来过，不是次数。

2. 为什么只查到 n+1 就够了？

数组只有 4 个格子，最多装下 4 个不同正整数。如果 1、2、3、4 都来了，四格全用完，5 必然没来；如果它们中间已经有缺口，答案更小。因此 n 个数的答案一定不超过 n+1。

输入元素	要不要记录	seen[1]、seen[2]、seen[3]、seen[4]
开始	全部没见过	假，假，假，假
3	记录 3	假，假，真，假
4	记录 4	假，假，真，真
-1	忽略，不在 1..4	不变
1	记录 1	真，假，真，真
从 1 起查	1 来过，2 没来过	返回 2

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

int smallestMissingPositive(int A[], int n) {
    bool *seen = (bool *)calloc(n + 1, sizeof(bool));
    if (seen == NULL)
        return -1;

    for (int i = 0; i < n; i++) {
        if (A[i] > 0 && A[i] <= n)
            seen[A[i]] = true;
    }

    int answer = n + 1;
    for (int value = 1; value <= n; value++) {
        if (!seen[value]) {
            answer = value;
            break;
        }
    }

    free(seen);
    return answer;
}

分配 n+1 格是为了让下标 n 也可使用：实际下标为 0..n，其中 0 这格不用。分配失败的 -1 只是错误信号，不是一个正整数答案。

第一个 for 扫输入，if 的两个条件同时成立才写 seen，防止负数或太大的数字越界。seen[A[i]]=true 重复执行也没问题，同一个人签到两次仍只是“来过”。

answer=n+1 是先假设 1..n 全到了。第二个 for 从 value=1 向上，!seen[value] 就是“没到”；第一次没到便记录并 break，所以得到的是最小的缺失数。最后释放标记数组，交回答案。

4. 自己试一下

[1,1,2] 的答案是 3，不是 4；重复的 1 占了格子，不能算成“已经见过三个正整数”。[-5,0,100] 中没有 1，所以答案为 1。我们忽略 100，不是说它不存在，而是说它不影响最先缺的是谁。

学懂后回看：结论、复杂度与回源

题意与结论：找数组中没出现的最小正整数。答案必在 1..n+1，只需标记 1..n 是否出现。

思路推导：从 1 开始，每试一个数就扫描一遍数组，最坏 O(n²)。为什么能只开 n+1 个标记位？数组只有 n 个位置：若 1..n 全出现，答案是 n+1；否则其中最先缺的就是答案。负数、0 和大于 n 的数不影响这些候选。

走一遍：[3,4,-1,1]，n=4。标记 seen[3]、seen[4]、seen[1]，忽略 -1。从 1 检查，1 在、2 不在，所以返回 2。[1,2,3] 的 1 到 3 都在，返回 4。

代码抓手与正确性：仅当 1<=A[i] && A[i]<=n 时写标记；扫描候选从 1 开始，不从 0 开始。重复值只是反复把同一标记设为真，不会浪费新的候选位置。

复杂度与易错点：初始化、扫描原数组、扫描标记合计 O(n)；空间 O(n)。空数组的数学答案是 1。这里没有要求保留一个负数作为失败答案；若分配失败，应另按函数约定处理，不能把错误返回值解释成缺失正整数。

回源：PDF 第 6 页；回源 · PDF 第 6 页 · b_6_2；PDF 第 6 页 · b_6_7 。正式代码

09｜两个升序表合并为升序（本章第 9 题）

题目与要求

题目（依据原题整理）：将两个已经递增有序的顺序表 A、B 合并成一个递增有序顺序表 C。

已知条件：A、B 各自有序，长度可不同。这里按允许相等的非递减顺序理解“递增”。

需要得到：C 包含两个表的全部元素，按从小到大排列，新表长等于两表长度之和。

输入 → 输出示例（教学补充）：A=[1,3,5]，B=[2,3] → C=[1,2,3,3,5]。

约定与提醒（教学补充）：这是合并，不是集合并集，重复元素也要保留。结果表应单独提供，且容量至少能容纳全部元素；本章定长结构不能越界写入。

题干回源：Code59 PDF 第 2、6 页；回源 · PDF 第 2 页 · b_2_12；PDF 第 6 页 · b_6_3 。

1. 两排已经站好次序的人，合成一排

A=[1,4,7]、B=[2,4,8]，目标 C=[1,2,4,4,7,8]。输入两表各自有序，前面最小，后面更大；只比较两排当前排头就能选出下一个最小者。

i 指 A 下一个待取位置，j 指 B 下一个待取位置，k 指 C 下一次放哪里。刚开始三个都是 0。

2. 每一轮只拿走一个数

比较前 i、j、k	比较值	选谁写 C[k]	写后 i、j、k
0、0、0	1 与 2	A 的 1	1、0、1
1、0、1	4 与 2	B 的 2	1、1、2
1、1、2	4 与 4	按 <= 先取 A 的 4	2、1、3
2、1、3	7 与 4	B 的 4	2、2、4
2、2、4	7 与 8	A 的 7	3、2、5
A 已用尽	B 还剩 8	直接补到 C[5]	3、3、6

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

void mergeAscending(SqList A, SqList B, SqList *C) {
    int i = 0, j = 0, k = 0;

    while (i < A.length && j < B.length) {
        if (A.data[i] <= B.data[j])
            C->data[k++] = A.data[i++];
        else
            C->data[k++] = B.data[j++];
    }
    while (i < A.length)
        C->data[k++] = A.data[i++];
    while (j < B.length)
        C->data[k++] = B.data[j++];

    C->length = k;
}

函数不交回一个整数，而是通过 C 指针修改结果表。主 while 的 && 意味着两张表都还有数，才有资格互相比较；一方结束后继续比较会越界。

若 A 当前值不大于 B 当前值，执行 C->data[k++]=A.data[i++]：先写 C[k]，然后 k、i 各加一，j 不动。else 完全对称。不能两边读指针同时前进，否则没被选的值被漏掉。

后两个 while 是补尾巴，实际至多一个有剩余。因为另一边已经空了，剩余这边自己有序，直接连续复制即可。最后 C->length=k，k 正是总共放进结果的数目。

4. 自己试，注意不是并集

A=[1,1]、B=[1]，C 必须有三个 1。本题只合并，不去重。若 B 为空，主循环不进，补 A 的循环直接复制 A。完整输出要有足够容量，此例容量至少 6。

学懂后回看：结论、复杂度与回源

题意与结论：把两张已排序表中的全部元素合成一张升序表。双指针分别指向两个表尚未使用的最小值，取较小者写入结果。

思路推导：拼接后排序忽略了已有的有序性。两张表各自的最小剩余元素都在表头，比较这两个就能找到全局最小剩余元素，无须看更后面。

走一遍：A=[1,4,7]，B=[2,4,8]。依次取 A的1、B的2、A的4、B的4、A的7；A 用完后，把 B 剩下的 8 补入，得到 [1,2,4,4,7,8]。

代码抓手与正确性：i、j 是输入读指针，k 是输出写指针。只移动被选中一方的读指针。主循环用 i<m && j<n，之后两个补尾循环缺一不可。每轮输出当前最小剩余值，所以输出前缀始终有序。

复杂度与易错点：时间 O(m+n)；输出数组占 O(m+n)，除此之外工作空间 O(1)。重复元素默认全部保留，不是集合并集。结果容量至少为 m+n，通常假定输出存储不与输入重叠；空表直接复制另一张。

回源：PDF 第 2 页目录、第 6 页正文；回源 · PDF 第 2 页 · b_2_12；PDF 第 6 页 · b_6_3 。正式代码

10｜两个升序表合并为降序（本章第 10 题）

题目与要求

题目（依据原题整理）：将两个已经递增有序的顺序表 A、B 合并成一个递减有序顺序表 C。

已知条件：输入的两个表都是从小到大排列，长度可以不同；本讲解允许相等元素。

需要得到：把两个输入表的全部元素放入 C，按从大到小排列，表长为两表长度之和。

输入 → 输出示例（教学补充）：A=[1,3,5]，B=[2,3] → C=[5,3,3,2,1]。

约定与提醒（教学补充）：输入升序、输出降序，别把这两个方向看反；重复值要保留。结果表需要足够容量，且下面代码不把它与输入表重叠使用。

题干回源：Code59 PDF 第 2、6 页；回源 · PDF 第 2 页 · b_2_13；PDF 第 6 页 · b_6_3 。

1. 输入升序，输出却要从大到小

仍用 A=[1,4,7]、B=[2,4,8]，这次目标 [8,7,4,4,2,1]。从两张表尾部开始取，因为最大的数在末尾。结果 C 仍从下标 0 往右写。

2. 分清“读向左”和“写向右”

比较前 i、j、k	当前两值	取值	下一轮 i、j、k
2、2、0	7、8	8	2、1、1
2、1、1	7、4	7	1、1、2
1、1、2	4、4	A 的 4	0、1、3
0、1、3	1、4	B 的 4	0、0、4
0、0、4	1、2	2	0、-1、5
B 已空	A 剩 1	1	-1、-1、6

i 或 j 变 -1 表示它已经从首元素左边越过去，不再对应可读位置；不是数组里有一个下标 -1 的格子。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

void mergeDescending(SqList A, SqList B, SqList *C) {
    int i = A.length - 1;
    int j = B.length - 1;
    int k = 0;

    while (i >= 0 && j >= 0) {
        if (A.data[i] >= B.data[j])
            C->data[k++] = A.data[i--];
        else
            C->data[k++] = B.data[j--];
    }
    while (i >= 0)
        C->data[k++] = A.data[i--];
    while (j >= 0)
        C->data[k++] = B.data[j--];

    C->length = k;
}

初始化 i、j 为各表 length-1；k=0。主循环的条件是两个读下标都仍非负。比较用 >=，当前更大的先输出；取 A 时 i--，取 B 时 j--，但结果位置 k 永远加一。

C->data[k++]=A.data[i--] 先按旧 k、i 复制，再调整两个下标。补尾循环也必须从剩余表的当前尾向左走，不能突然改为从头正向复制。最后结果长度仍为 k。

4. 自己试一下

A=[1,5]，B=[3]：先 5、再 3、最后补 1。若仍从两表头开始取较大者，会先取 3，却漏了 A 后面更大的 5，这是错误的。升序输入并不意味着任何位置都可以随便挑。

学懂后回看：结论、复杂度与回源

题意与结论：输入仍是升序，输出要降序。把两个读指针放在各自表尾，每次取较大值写到结果的下一个位置。

思路推导：上一题从最小端取小，本题从最大端取大。无需先做升序归并再整体逆置，虽然那也可行，但可以一步完成。

走一遍：A=[1,4,7]，B=[2,4,8]。先比较 7、8，取 8；比较 7、4，取 7；两边都是 4，依正式比较规则取一边，再取另一边；最后取 2、1，得到 [8,7,4,4,2,1]。

代码抓手与正确性：i=m-1，j=n-1，k=0；取 A 后 i--，取 B 后 j--，输出 k++。各表尾是其剩余部分最大值，故取二者之大就是全局最大剩余值。

复杂度与易错点：时间 O(m+n)，除输出外工作空间 O(1)。循环条件是下标仍 >=0；不能直接用无符号下标减到 -1 再判断。保留重复值，容量与不重叠假设同上一题。

回源：PDF 第 2 页目录、第 6 页正文；回源 · PDF 第 2 页 · b_2_13；PDF 第 6 页 · b_6_3 。正式代码

11｜三个升序无重复序列的公共元素（本章第 11 题）

题目与要求

题目（依据原题整理）：给定三个长度均为 n 的递增序列 A、B、C，每个序列内部没有重复元素。设计尽可能高效的算法，输出三个序列中共同存在的所有元素。

已知条件：三个序列各自有序且内部无重复；一个值可以同时出现在不同序列中。

需要得到：三者的交集，即在 A、B、C 中都能找到的值，而不是只在其中两个序列出现的值。

输入 → 输出示例（教学补充）：A=[1,3,5]，B=[2,3,5]，C=[3,4,5] → 依次输出 3、5。

约定与提醒（教学补充）：没有公共元素时不输出元素，不能用 0 代替“没有”，因为 0 也可能是合法数据。下面函数直接打印公共元素，不返回新数组。

题干回源：Code59 PDF 第 7 页；回源 · PDF 第 7 页 · b_7_0；PDF 第 7 页 · b_7_1 。

1. “公共元素”是三份名单里都有的数

A=[1,3,5]、B=[2,3,5]、C=[3,4,5]，输出 3 和 5，不输出只出现两次或一次的数。每份名单已经升序且内部无重复。

i、j、k 分别是三份名单的读位置。它们可以走得不一样快，不是每次都一起加一。

2. 落后的数为什么可以丢掉？

当前 A[i]、B[j]、C[k]	是否全相同	当前最大值	动作
1、2、3	否	3	A 的 1、B 的 2 都落后，各前进一步
3、3、3	是	—	打印 3，三方都前进
5、5、4	否	5	只移动 C
5、5、5	是	—	打印 5，三方都到末尾之外

第一轮 C 已经读到 3，后面只会更大，所以 A 的 1 再等也不可能与 C 相同；B 的 2 同理。这个判断靠有序，而不是凭感觉“追大数”。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

int max3(int a, int b, int c) {
    int maxValue = a;
    if (b > maxValue) maxValue = b;
    if (c > maxValue) maxValue = c;
    return maxValue;
}

void printCommonElements(int A[], int B[], int C[], int n) {
    int i = 0, j = 0, k = 0;

    while (i < n && j < n && k < n) {
        if (A[i] == B[j] && A[i] == C[k]) {
            printf("%d ", A[i]);
            i++;
            j++;
            k++;
        } else {
            int maxValue = max3(A[i], B[j], C[k]);
            if (A[i] < maxValue) i++;
            if (B[j] < maxValue) j++;
            if (C[k] < maxValue) k++;
        }
    }
}

max3 是辅助任务：先假设 a 最大；b 更大就更新；c 更大再更新；return 最大值。两个 if 都需要执行，c 的比较要用可能已更新的 maxValue。

主函数先把三个下标设 0；while 要求三表都还有可读数。一旦全相等，就 printf 输出该数，再三者各加一，否则同一个公共数会重复输出，循环也不前进。

不全等时计算当前 maxValue，再做三个独立 if：哪一个小于 maxValue，哪一个就前进。它们不是互斥的选择，第一轮必须允许 A、B 同时前进。任何一表结束就停止，因为已没有可能被三表共同配出的新值。

4. 自己试一下

A=[1,4]、B=[2,4]、C=[3,4]：开始 (1,2,3)，A、B 前进成 (4,4,3)；C 前进后全为 4，输出 4。三个指针各最多走 n 次，总共最多约 3n 次前进，不是 n³ 次组合。

学懂后回看：结论、复杂度与回源

题意与结论：三个序列各用一个指针。当前值全相等就输出并共同前进；不相等时，让低于当前最大值的指针向前追赶。

思路推导：三重枚举是 O(n³)。有序性告诉我们：若当前最大值为 5，而某个序列当前为 2，另外那个已到 5 的序列以后不会再出现 2，所以这个 2 不可能是公共元素，可以安全丢弃。

走一遍：A=[1,3,5]，B=[2,3,5]，C=[3,4,5]。当前 (1,2,3)，A、B 各前进一步，变 (3,3,3)，输出 3，三指针一起走。接着 (5,5,4)，仅 C 前进，变 (5,5,5)，输出 5。

代码抓手与正确性：正式代码计算本轮最大值 maxValue，用三个独立的 if 移动所有较小者，而不是只允许一个分支执行的 else if。每个指针只前进、不回退，丢弃的值都有“另一序列再也不会遇见它”的依据。

复杂度与易错点：三表等长为 n 时总时间 O(n)，空间 O(1)，不是“有三个指针就立方”。不同长度时为 O(n1+n2+n3)。任一表结束即可停止；题设各表无重复，所以输出不另去重。正式版已修复求最大值时并列最大处理错误。

回源：PDF 第 7 页；回源 · PDF 第 7 页 · b_7_2；PDF 第 7 页 · b_7_0；PDF 第 7 页 · b_7_1；PDF 第 7 页 · b_7_6 。正式代码

12｜三个集合的最小三元组距离（本章第 12 题，2020）

题目与要求

题目（依据原题整理）：三个非空整数集合 S1、S2、S3 分别按升序存放在数组中。从每个集合各选一个数 a、b、c，三元组距离定义为 D=|a-b|+|b-c|+|c-a|。设计尽可能高效的算法，求所有选择中的最小距离。

已知条件：三数组分别长 m、n、p，都非空、都有序；数值可以为负。

需要得到：最小的距离数值。下面函数不额外返回是哪三个数取得了该距离。

输入 → 输出示例（教学补充）：S1=[1,5]，S2=[2,6]，S3=[3,7] → 4，例如选 (1,2,3) 得到 1+1+2=4。

约定与提醒（教学补充）：三元组必须从三个不同集合各取一个数；距离不是下标之差。代码中的整数运算须在可表示范围内，不能把极大整数溢出当作合法距离。

题干回源：Code59 PDF 第 7 页；回源 · PDF 第 7 页 · b_7_3 。

1. 三元组就是“从三张表各拿一个数”

从 S1、S2、S3 各取 a、b、c，距离定义为三个两两差的绝对值之和。绝对值表示数轴上不带方向的距离，例如 |2-5|=3。目标是所有组合中距离最小，不要求三个数本身最小。

如果 a<=b<=c，式子成为 (b-a)+(c-b)+(c-a)=2(c-a)。中间的 b 抵消掉了，因此只要缩小最大、最小之间的间隔。

2. 小例子把每一组都算到停

输入 S1=[1,4,10]，S2=[2,15]，S3=[3,12]。

i、j、k	当前三数	三个差相加	目前最好	下一步
0、0、0	1、2、3	1+1+2=4	4	1 最小，i++
1、0、0	4、2、3	2+1+1=4	4	2 最小，j++
1、1、0	4、15、3	11+12+1=24	4	3 最小，k++
1、1、1	4、15、12	11+3+8=22	4	4 最小，i++
2、1、1	10、15、12	5+3+2=10	4	10 最小，i 到 3，S1 用尽

答案是记住的 4，不是最后算出的 10。distance 只管本轮；minDistance 记历史最好，二者必须分开。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

int minTripleDistance(int S1[], int m,
                      int S2[], int n,
                      int S3[], int p) {
    int i = 0, j = 0, k = 0;
    int minDistance = INT_MAX;

    while (i < m && j < n && k < p) {
        int distance = abs(S1[i] - S2[j])
                     + abs(S2[j] - S3[k])
                     + abs(S3[k] - S1[i]);

        if (distance < minDistance)
            minDistance = distance;

        if (S1[i] <= S2[j] && S1[i] <= S3[k])
            i++;
        else if (S2[j] <= S1[i] && S2[j] <= S3[k])
            j++;
        else
            k++;
    }

    return minDistance;
}

三个长度分别是 m、n、p，不一定相等。minDistance 初始为 INT_MAX，可看作先设一个非常大的上限，让第一组正常距离能替换它。while 要求三个读下标都有效。

distance 的三行其实是一条加法赋值，分行只是方便阅读；abs 取绝对值。如果本次更小才更新历史纪录，然后用 if/else if/else 找一个最小值指针前进：S1 不大于另外两个就移 i；否则若 S2 不大于另外两个就移 j；剩下是 S3，移 k。这里相等时选一个最小者移动就足够。

4. 为什么不是移动最大值？自己试一下

固定最小数 1，把最大数从 3 换成更大的 12，间隔只会增大。只有尝试把较小一端往上抬，才可能缩小跨度。更严谨地说：保留当前最小值不动而只增加另外两值，不可能优于刚算过的组合，所以可以淘汰它。

练习 S1=[2]、S2=[2]、S3=[2]：距离 0，是不可能再小的答案。三集合要非空，计算范围需不溢出；不是所有看似相似的三数组题都能用这个最小值移动规则。

学懂后回看：结论、复杂度与回源

题意与结论：各取一个数，使 D=|a-b|+|b-c|+|c-a| 最小。若排序后为 x<=y<=z，则 D=(y-x)+(z-y)+(z-x)=2(z-x)，所以核心是缩小最大值与最小值之间的跨度。

思路推导：暴力逐一尝试全部组合，时间 O(mnp)。三个升序数组各用一个指针，算当前距离并更新答案，然后前移当前最小值的一方。固定这个最小值而只移动另两方，最小值不会变大，最大值不会变小，距离不可能下降；所以当前最小值已没有继续保留的价值。

走一遍：S1=[1,4,10]，S2=[2,15]，S3=[3,12]。初始 (1,2,3)，距离 4；移动最小值 1，得到 (4,2,3)，距离仍为 4；再移动 2，得到 (4,15,3)，距离 24。后面还有 (4,15,12) 距离 22、(10,15,12) 距离 10，所以最小值为 4。

代码抓手与正确性：先计算当前组合、更新最优值，再移动一个最小值指针。并列最小时任选其中一方前进也成立。证明重点不是“看起来往中间挤”，而是上述被丢弃候选不可能产生更优组合。

复杂度与易错点：时间 O(m+n+p)，空间 O(1)；三集合非空、有序。某一数组用尽后即可结束，因为它最后一个当前值已完成相应淘汰比较。距离非负，算出 0 就是全局最优。工程大数范围下应使用足够宽的整数，防止差值、绝对值与乘 2 溢出。

回源：PDF 第 7 页；回源 · PDF 第 7 页 · b_7_3；PDF 第 7 页 · b_7_7 。正式代码

13｜两个等长升序序列的中位数（本章第 13 题，2011）

题目与要求

题目（依据原题整理）：一个长度为 L 的升序序列，把第 ⌈L/2⌉ 个元素称为中位数（位置从 1 开始数）。现有两个等长的升序序列 A、B，设计时间和空间都尽可能高效的算法，找出它们合在一起后的中位数。

已知条件：两个序列长度都为 n 且 n>0，各自已按升序排列。

需要得到：合并排序后 2n 个元素中的第 n 小元素，即中间两个数里较小的那个。

输入 → 输出示例（教学补充）：A=[1,3,5]，B=[2,4,6] → 3；合并后的第 3 个数是 3。

约定与提醒（教学补充）：这里不是统计学中偶数项取两中间值平均数的约定，因此示例答案不是 3.5。原资料采用归并；下面讲解锁定校订稿的折半实现，不把它冒充原稿代码。

题干回源：Code59 PDF 第 8 页；回源 · PDF 第 8 页 · b_8_2 。

1. 先确认要的是“第几个”，再谈折半

两张表各有 n 个数，合起来共 2n 个。本题要第 n 小的那个。例如合并为 [1,2,3,4,5,6,7,8] 时要第 4 个即 4，不要 (4+5)/2=4.5。

先想容易的办法：两表归并后读第 n 个。它能帮你理解答案，但正式代码进一步利用有序性，一次排除两端一批数，不真正合并数组。

2. 四个边界变量先画成两条线

s1、d1 是 A 当前保留段的左、右下标，s2、d2 是 B 的；四个端点都包括。m1、m2 是两段靠左的中点。改变 s、d 只是缩小考虑范围，不会修改原数组元素。

步骤	A 候选区间	B 候选区间	比较中点	留下什么
初始	[1,3,5,7]，下标 0..3	[2,4,6,8]，下标 0..3	3<4，段长 4 为偶数	A 留 5、7；B 留 2、4
第二轮	下标 2..3 的 [5,7]	下标 0..1 的 [2,4]	5>2，段长 2 为偶数	A 留 5；B 留 4
停止	只剩 5	只剩 4	不再折半	取较小值 4

第一轮是同时从小端、高端各去掉两个；原问题要第 4 小，去掉小端两个之后，新问题要剩余四数里的第 2 小，仍是“下中位数”。算法每次保持这样的目标形式。

3. 奇数与偶数到底差在哪

若两段都是 5 个，中点左右各有 2 个；A 中点小于 B 中点时，A 去掉中点前的 2 个、B 去掉中点后的 2 个，中点都保留，各剩 3 个。

若两段都是 4 个，取靠左中点：它左侧 1 个、右侧 2 个。要使淘汰数量相同，就让 A 把小中点一起扔掉（共 2 个），B 扔掉大中点之后的 2 个。于是 A 从 m1+1 开始，B 到 m2 结束。

注意这里说“小端/高端”是利用两段有序与中点大小关系安全成对排除，不是声称被扔掉的低端每个数都小于整个剩余区所有数。

4. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

int medianOfTwoEqualSortedArrays(int A[], int B[], int n) {
    int s1 = 0, d1 = n - 1;
    int s2 = 0, d2 = n - 1;

    while (s1 != d1) {
        int m1 = (s1 + d1) / 2;
        int m2 = (s2 + d2) / 2;

        if (A[m1] == B[m2])
            return A[m1];

        if (A[m1] < B[m2]) {
            if ((s1 + d1) % 2 == 0) {
                s1 = m1;
                d2 = m2;
            } else {
                s1 = m1 + 1;
                d2 = m2;
            }
        } else {
            if ((s2 + d2) % 2 == 0) {
                d1 = m1;
                s2 = m2;
            } else {
                d1 = m1;
                s2 = m2 + 1;
            }
        }
    }

    return A[s1] < B[s2] ? A[s1] : B[s2];
}

先将两候选段设为完整 [0,n-1]。while(s1!=d1) 表示 A 还不止一个数；因为两段一直等长，B 也一样。每轮重新计算 m1、m2，不能沿用上一轮中点。

若 A[m1]==B[m2]，共同中值就是答案，直接返回。若 A 中点更小，保留 A 较大部分和 B 较小部分；(s1+d1)%2==0 说明端点和为偶数，等价于长度 d1-s1+1 为奇数，于是中点都留。否则用 m1+1 跳过小中点。A 中点更大时完全对称：缩 A 的右端，抬 B 的左端。

最后三目运算符 条件?A:B 表示两候选各剩一个后取较小者。总共两数的下中位数当然是第一个，因此不是取平均值，也不是取较大值。

5. 自己试：先别盲背奇偶分支

A=[1,3,5]、B=[2,4,6]。第一轮 3<4，长度 3 为奇数，保留 [3,5]、[2,4]；第二轮 3>2、长度 2 为偶数，保留 [3]、[4]，返回 3。若第一轮错把 A 的中点 3 扔了，正确答案已经丢掉。

初学时先用归并手工验证目标，再模拟四个端点变化；不要急着只记 s=m+1。两个数组必须等长且非空，这份模板不直接解决不等长版本。

学懂后回看：结论、复杂度与回源

题意与结论：合并后有 2n 个数，本题要第 n 小，即两个中间数中较小的那个，不是两数平均值。用两个等长候选区间反复折半，时间 O(log n)。

思路推导：完整归并可求，但用掉 O(n) 时间。设两区间的中间值为 a、b，若 a<b，可以成对去掉 A 的低端与 B 的高端；去掉同样多的小端和大端元素，不会改变剩余问题的“下中位数”。若 a>b，对称处理。

走一遍（偶数长度）：A=[1,3,5,7]，B=[2,4,6,8]。中间下标均为 1，比较 3<4，保留 A=[5,7]、B=[2,4]。现在比较 5>2，保留 A=[5]、B=[4]。两者较小为 4；原合并序列第 4 个确实是 4。

走一遍（奇数长度）：A=[1,3,5]，B=[2,4,6]。比较 3<4，保留 [3,5]、[2,4]，这次 A 的中点 3 不能扔。再比较 3>2，保留 [3]、[4]，结果为 3。

代码抓手与正确性：s1,d1,s2,d2 都是闭区间端点。区间长度为奇数时保留相关中点；偶数时，从较小中间值那一侧去掉中点，保证两边剩余长度相等。代码的 (s+d)%2==0 等价于区间长度为奇数。中间值相等立即返回；各剩一个时取 min。

复杂度与易错点：时间 O(log n)、空间 O(1)，前提 n>=1、两个数组等长且有序。不要直接套到不等长数组；不要返回平均值；不要把奇偶分支交换。正式校订版已经替换原稿的完整归并法。

回源：PDF 第 8 页；回源 · PDF 第 8 页 · b_8_2；PDF 第 8 页 · b_8_9 。正式代码

14｜负数在前、非负数在后（本章第 14 题）

题目与要求

题目（依据原题整理）：调整整数数组中的元素位置，使所有负数都在数组前面，所有非负数都在后面。

已知条件：输入一个整数数组及其长度；0 属于非负数。

需要得到：元素不增不减，任意负数都排在任意非负数之前；各组内部不要求按大小排序。

输入 → 输出示例（教学补充）：[2,-1,0,-3] → 一种合法结果为 [-3,-1,0,2]。

约定与提醒（教学补充）：合法结果通常不唯一。本题没有要求保持组内原相对次序，下面的交换法也不保证这一点；不能拿“稳定拆分”的要求来判它错误。

题干回源：Code59 PDF 第 8 页；回源 · PDF 第 8 页 · b_8_4；PDF 第 8 页 · b_8_3 。

1. 只分左右两堆，不负责堆内排序

输入 [2,-1,0,-3,4]，一种合格输出是 [-3,-1,0,2,4]。所有负数在前，所有非负数在后即可；0 属于非负数。-3 与 -1 谁先谁后没有要求。

left 从左边找“不该放在负数区的数”，right 从右边找“不该放在非负区的数”，两者互换，一次同时纠正两个位置。

2. 两只手如何相遇

步骤	left	right	数组与说明
初始	0	4	左边 2 非负，先停；右边 4 非负，已经对了
右边找负数	0	3	-3 是负数，停在这里
交换	0	3	[-3,-1,0,2,4]
下一轮左扫	2	3	越过 -3、-1，停在 0
下一轮右扫	2	2	越过 2，指针相遇，不再交换

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

void partitionBySign(int A[], int n) {
    int left = 0;
    int right = n - 1;

    while (left < right) {
        while (left < right && A[left] < 0)
            left++;
        while (left < right && A[right] >= 0)
            right--;

        if (left < right) {
            int temp = A[left];
            A[left] = A[right];
            A[right] = temp;
        }
    }
}

两个初始化给出有效两端。外层 while 表示还有一段未分好的区间；左内层 while 遇负数就 left++，直到找到非负数或两指针相遇；右内层反过来，遇非负数就 right--。

只有 left<right 仍成立才交换，否则两只手已经碰上。temp 暂存左值，再把右值放左边、旧左值放右边。代码交换后没有立刻 left++、right--；下一轮的两个内循环会跳过刚刚已归位的数，所以仍能推进。

4. 自己试一下

[0,-2] 交换后是 [-2,0]。如果全是负数，左手一路走到右端，不发生交换，已满足要求。若另要求原负数次序不能变，则本法不满足；例子中 -3 原来在 -1 后面，现在跑到了前面。

学懂后回看：结论、复杂度与回源

题意与结论：只按符号分区，不要求各区内部排序。左指针找放错位置的非负数，右指针找放错位置的负数，交换即可。

思路推导：左端已经是负数就不用管；右端已经非负也不用管。两端都停住时，正好是一对能够互相纠正位置的元素。

走一遍：[2,-1,0,-3,4]。左指针停在 2，右指针越过 4 停在 -3，交换为 [-3,-1,0,2,4]。继续扫描，左边越过 -3、-1，右边越过非负部分，指针相遇，结束。

代码抓手与正确性：每次内层扫描都先判断 left<right。不变量是：左指针之前全为负数，右指针之后全为非负数；每轮扩大两个已正确分区。指针相遇时，没有未分类区间了。

复杂度与易错点：时间 O(n)、空间 O(1)。0 属于非负区。该方法不稳定，例如例子中 -3 跑到了原先更靠前的 -1 前面；若要求保持相对次序，这是另一种约束，不能声称本法满足。

回源：PDF 第 8 页；回源 · PDF 第 8 页 · b_8_4；PDF 第 8 页 · b_8_3；PDF 第 8 页 · b_8_7 。正式代码

15｜每个位置的后缀最大乘积（本章第 15 题，2025）

题目与要求

题目（依据原题整理）：给定长度为 n 的整数数组 A 和结果数组 res。对每个位置 i，在 i<=j<=n-1 的范围内选择 j，把乘积 A[i]*A[j] 的最大值存入 res[i]。设计时间和空间上尽可能高效的算法。

已知条件：两个数组长度均为 n，n>=1，A 中可有正数、负数和 0；下标从 0 开始。

需要得到：长度为 n 的整个结果数组，不是一个全局最大乘积。

输入 → 输出示例（教学补充）：A=[1,4,-9,6] → res=[6,24,81,36]。例如 res[2] 在 (-9)*(-9) 和 (-9)*6 中取 81。

约定与提醒（教学补充）：允许 j=i，因此可以和自己相乘；不允许选 i 左边的元素。下面原样保留的函数使用 int 运算并保存结果，输入必须保证乘积不溢出；若扩大数值范围，需要另外采用宽整数实现。输出数组不与输入数组重叠。

题干回源：Code59 PDF 第 9 页；回源 · PDF 第 9 页 · b_9_0 。

1. 先固定 i，再问允许和谁相乘

输入 A=[1,4,-9,6]。对于 i=1 的数 4，允许搭配它自己和右边的 4、-9、6，不允许回头搭配左边的 1。算 16、-36、24，最大是 24，放入 res[1]。

“后缀”就是从当前位置直到最后这一段，含当前位置。每个 i 都要一个答案，所以 res 和 A 一样长。

2. 从最右边做起，把极值带给左边

i	当前 A[i]	本轮允许的后缀	后缀最小、最大	选择乘谁	res[i]
3	6	[6]	6、6	6	36
2	-9	[-9,6]	-9、6	最小的 -9	81
1	4	[4,-9,6]	-9、6	最大的 6	24
0	1	[1,4,-9,6]	-9、6	最大的 6	6

最后按正常下标顺序读 res，是 [6,24,81,36]，不是按计算先后顺序把它倒着抄。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

void calculateMaxProducts(int A[], int res[], int n) {
    int suffixMax = A[n - 1];
    int suffixMin = A[n - 1];
    res[n - 1] = A[n - 1] * A[n - 1];

    for (int i = n - 2; i >= 0; i--) {
        if (A[i] > suffixMax) suffixMax = A[i];
        if (A[i] < suffixMin) suffixMin = A[i];

        if (A[i] >= 0)
            res[i] = A[i] * suffixMax;
        else
            res[i] = A[i] * suffixMin;
    }
}

先取末元素初始化 suffixMax、suffixMin，并单独填末答案。for 从 n-2 开始向左，每轮先比较 A[i] 是否突破旧最大/最小值；两个 if 独立执行，让变量准确描述包括本人的新后缀。

然后看 A[i] 的符号：非负乘数不改变大小方向，乘后缀最大值最优；负数乘法反转大小方向，乘后缀最小值最优。例如 -2×-9=18 大于 -2×6=-12。结果直接写入 res[i]，函数返回类型 void，不需要额外 return 一个数。

4. 自己试：顺序反过来会错哪一个？

如果先计算后更新极值，处理 -9 时只知道旧后缀 [6]，会误写 -54，漏掉与自己相乘得到的 81。练习 [-2,-3]：末答案 9；左边 -2 乘后缀最小 -3 得 6，结果 [6,9]。允许自己相乘不代表自己相乘永远最优。

学懂后回看：结论、复杂度与回源

题意与结论：对每个 i 求 max{A[i]*A[j] | i<=j<n}。右往左扫描，维护当前后缀的最大值和最小值；正数乘最大值，负数乘最小值。

思路推导：每个位置再扫一遍后缀是 O(n²)。相邻后缀只多一个元素，极值可以复用。为什么需要最小值？因为乘负数会反转大小关系：-2×(-9)=18 大于 -2×6=-12。

走一遍：A=[1,4,-9,6]。从右边开始：i=3，后缀只有 6，结果 36；i=2，后缀最小 -9、最大 6，-9×(-9)=81；i=1，最大仍是 6，结果 24；i=0，结果 6。最终 res=[6,24,81,36]。

代码抓手与正确性：先把 A[i] 纳入 suffixMin/suffixMax，再求乘积，因为 j=i 被允许。若反过来，会错误地排除自己，例如例子中的 81 就算不出来。扫描到 i 时，两个变量精确代表 A[i..n-1] 的极值；固定乘数后，乘积最值一定落在对应端点。

复杂度与易错点：时间 O(n)；输出数组 O(n)，其余工作空间 O(1)。0 的结果为 0。正式实现要求 n>=1。答案不是整个数组任意两数最大乘积，也不是只允许 j>i；实际代码若数据较大，乘法两侧及输出类型都应支持宽整数。

回源：PDF 第 9 页；回源 · PDF 第 9 页 · b_9_0；PDF 第 9 页 · b_9_2；PDF 第 9 页 · b_9_12 。正式代码