第2章 顺序表与数组算法
第2章 顺序表与数组算法¶
方法总路线：先保底，再榨干条件¶
面对数组算法题，考场上怎样按步骤落笔？¶
何时用：所有“设计一个时间上尽可能高效的算法”题。尤其适合一时看不出最优解、但能写出枚举或排序解时。
思路步骤：
- 先写正确的暴力解，明确输入、输出和循环边界，拿到基本分。
- 再列出尚未使用的条件：有序、值域小、只求第 k 小、只查边界、元素非负、空间限制等。
- 检查是否做了“超额工作”：只要中位数却全排序，只要交集却两重枚举，只要区间和却反复求和。
- 选用对应工具：有序性→折半/双指针；有限值域→直接寻址；重复区间查询→预处理；只定位秩→Quickselect。
- 最后写正确性依据、复杂度与边界，不用“感觉能过”代替证明。
伪代码/关键模板：
复杂度：本卡是答题流程，本身无固定复杂度；复杂度取决于最终算法。
易错边界：不要在暴力解尚未闭环时孤注一掷追最优；题目若禁止改变原序、要求稳定或只读，不能直接原地快排。
b_5_0；PDF 第 5 页 · b_5_2；PDF 第 5 页 · b_5_11写出保底解后，怎样判断还能不能优化？¶
何时用：暴力解已经正确，但时间复杂度为 O(n²)、O(n³) 或 O(n log n)，题目又要求“尽可能高效”时。
思路步骤：
- 做“条件浪费”检查：升序是否还在顺扫？取值范围是否没有映射？非负性是否没有用于滑窗？
- 做“目标超额”检查：只找极值却全排序？只划分一侧却递归两侧？每次区间查询都重新累计？
- 把目标改写为单调判定、局部推进或可复用状态。
- 优化后重新证明：每次舍弃的区间是否一定无解；每个指针是否只单向移动；辅助数组下标是否覆盖完整值域。
伪代码/关键模板：
unused_condition = {有序, 值域, 非负, 重复查询, 只求一个秩}
extra_work = {全排序, 重复扫描, 重复求和, 搜索无效状态}
逐项匹配工具，并用不变式验证“舍弃部分不含答案”
复杂度：常见优化是 O(n²)→O(n)、O(n log n)→期望 O(n)、多次 O(n) 查询→预处理后 O(1) 查询。
易错边界：优化不是看到关键词就套模板；例如链表“有序”通常也不适合折半，滑窗计数依赖元素非负，直接寻址的空间是 O(M) 而不总是 O(n)。
b_9_3；PDF 第 9 页 · b_9_5；PDF 第 9 页 · b_9_7；PDF 第 9 页 · b_9_8分治选择：快排、划分与 Quickselect¶
快速排序什么时候能用，最坏界怎样写才准确？¶
何时用：允许改变数组顺序、不要求稳定，且“先排序再处理”能显著简化问题时。
思路步骤：
- 在闭区间 [lo, hi] 选枢轴。
- 划分后让枢轴进入最终位置 p，左侧不大于它，右侧不小于它。
- 递归处理 [lo, p-1] 与 [p+1, hi]。
- 用随机枢轴或三数取中降低持续极端划分的概率。
伪代码/关键模板：
static void ac_swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}
static int ac_partition(int a[], int lo, int hi) {
int pivot = a[lo];
int i = lo, j = hi;
while (i < j) {
while (i < j && a[j] >= pivot) --j;
while (i < j && a[i] <= pivot) ++i;
if (i < j) ac_swap(&a[i], &a[j]);
}
ac_swap(&a[lo], &a[i]);
return i;
}
static void ac_quick_sort(int a[], int lo, int hi) {
if (lo >= hi) return;
int p = ac_partition(a, lo, hi);
ac_quick_sort(a, lo, p - 1);
ac_quick_sort(a, p + 1, hi);
}
复杂度：平均时间 O(n log n)、平均递归栈 O(log n)；若每次只分出一个元素，最坏时间 O(n²)、最坏栈 O(n)。新版补充/校订：旧版只写了平均界，这里补齐最坏界。
易错边界：区间参数必须统一为闭区间；两侧扫描与比较符号必须配套，否则重复元素会卡死；禁止改序、要求稳定时不能直接用本模板。
b_8_0；PDF 第 8 页 · b_8_3；PDF 第 8 页 · b_8_4；PDF 第 8 页 · b_8_5；PDF 第 9 页 · b_9_2一次 partition 之后，真正保持了什么不变式？¶
何时用：需要手写快排、Quickselect，或只要求把“小于 k”和“大于等于 k”的元素分到两侧时。
思路步骤：
- 保存枢轴值，避免枢轴所在单元在交换中丢失。
- 在挖坑/交换过程中维护：已处理左段均不大于 pivot，已处理右段均不小于 pivot。
- i 与 j 相遇时，该位置是枢轴的最终位置。
- 若题目只要求二分集合，到此即可，不要继续排序两侧。
伪代码/关键模板：
复杂度：一次划分时间 O(hi-lo+1)，额外空间 O(1)。
易错边界：不同 partition 写法的“等号归哪侧”不可混搭；返回位置是枢轴最终秩，不代表左右内部已有序；只划分时不要误写成完整快排。
b_20_6；PDF 第 20 页 · b_20_9；PDF 第 21 页 · b_21_0；PDF 第 21 页 · b_21_3只求第 k 小时，为什么 Quickselect 不必排序两边？¶
何时用：只求第 k 小、中位数、或只需把较小的一半与较大的一半分开，且允许改变数组。
思路步骤：
- 把第 k 小换成目标下标 target=k-1。
- 对当前区间做 partition，得到枢轴最终下标 p。
- p=target 时直接结束；target<p 只保留左区间；否则只保留右区间。
- 迭代写法避免递归栈；随机化枢轴可降低退化概率。
伪代码/关键模板：
static int ac_quick_select(int a[], int n, int k) {
if (n <= 0 || k < 1 || k > n) return 0;
int lo = 0, hi = n - 1, target = k - 1;
while (lo <= hi) {
int p = ac_partition(a, lo, hi);
if (p == target) return a[p];
if (target < p) hi = p - 1;
else lo = p + 1;
}
return 0;
}
复杂度：随机或平均情况下期望 O(n)；固定坏枢轴时最坏 O(n²)。迭代版额外空间 O(1)；递归版平均栈 O(log n)、最坏 O(n)。新版补充/校订：不能把期望 O(n) 写成无条件最坏 O(n)。
易错边界：k 是从 1 计数还是下标必须先换算；Quickselect 只保证目标位置与两侧大小关系，不保证两侧内部有序；返回 0 不能表达所有错误场景，工程代码应另设状态值。
b_21_4；PDF 第 21 页 · b_21_7；PDF 第 21 页 · b_21_11；PDF 第 22 页 · b_22_1折半边界：区间定义先于代码¶
精确查值为什么推荐闭区间模板？¶
何时用：升序数组中查找某个确切值，找到任一位置即可。
思路步骤：
- 明确搜索区间始终是闭区间 [lo, hi]。
- 当 lo≤hi 时取中点；相等直接返回。
- 目标更小就令 hi=mid-1，更大就令 lo=mid+1。
- 区间为空时返回未找到。
伪代码/关键模板：
static int ac_binary_find(const int a[], int n, int x) {
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == x) return mid;
if (a[mid] < x) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
复杂度：时间 O(log n)，额外空间 O(1)。
易错边界：闭区间必须搭配 lo≤hi 和 mid±1；用 lo+(hi-lo)/2 避免 lo+hi 溢出；空数组时 hi=-1，循环自然不进入。
b_10_3；PDF 第 10 页 · b_10_8；PDF 第 11 页 · b_11_0lower_bound 怎样用半开区间稳定找左边界？¶
何时用：重复元素中找第一个不小于 x 的位置，也可作为“第一个等于 x”的候选位置。
思路步骤：
- 维护半开区间 [lo, hi)，初始 [0,n)。
- 若 a[mid]≥x，答案仍可能是 mid，令 hi=mid。
- 若 a[mid]<x，mid 不可能是答案，令 lo=mid+1。
- 退出时 lo=hi，即第一个不小于 x 的插入位置；再检查是否小于 n 且等于 x。
伪代码/关键模板：
static int ac_lower_bound(const int a[], int n, int x) {
int lo = 0, hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] >= x) hi = mid;
else lo = mid + 1;
}
return lo;
}
复杂度：时间 O(log n)，额外空间 O(1)。
易错边界：返回值可能等于 n，访问 a[pos] 前必须判界；保留 mid 时只能写 hi=mid，写成 mid-1 会漏掉真正边界；不要把闭区间和半开区间更新式混用。
b_11_1；PDF 第 11 页 · b_11_3；PDF 第 11 页 · b_11_5；PDF 第 12 页 · b_12_3统计 x 出现次数，怎样避免用 x+1 造成溢出？¶
何时用：有重复元素的升序数组中统计某值出现次数，或寻找等值段的左右边界。
思路步骤：
- lower_bound 找第一个 ≥x 的位置 left。
- upper_bound 直接找第一个 >x 的位置 right。
- 次数为 right-left；若不存在 x，两边会相等。
- 不用 lower_bound(x+1)，因为 x=INT_MAX 时会整数溢出。
伪代码/关键模板：
static int ac_upper_bound(const int a[], int n, int x) {
int lo = 0, hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] > x) hi = mid;
else lo = mid + 1;
}
return lo;
}
static int ac_count_occurrences(const int a[], int n, int x) {
return ac_upper_bound(a, n, x) - ac_lower_bound(a, n, x);
}
复杂度：两次折半，总时间 O(log n)，额外空间 O(1)。
易错边界：upper_bound 的判定是严格大于；不要在 right=n 时访问 a[right]。新版补充/校订：旧版用 x+1 求右界，x=INT_MAX 时可能溢出，本卡改为直接 upper_bound(x)。
b_53_2；PDF 第 54 页 · b_54_4；PDF 第 54 页 · b_54_6；PDF 第 55 页 · b_55_3；PDF 第 55 页 · b_55_5无重复旋转升序数组，最小值为何能二分？¶
何时用：数组由严格升序数组旋转而来、元素无重复，要求最小值或旋转点。
思路步骤：
- 维护最小值必在 [lo,hi]。
- 比较 a[mid] 与右端 a[hi]。
- a[mid]≤a[hi] 时，mid 到 hi 有序，最小值在 [lo,mid]，保留 mid。
- a[mid]>a[hi] 时，最小值在 [mid+1,hi]。
伪代码/关键模板：
static int ac_rotated_min_index(const int a[], int n) {
if (n <= 0) return -1;
int lo = 0, hi = n - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] <= a[hi]) hi = mid;
else lo = mid + 1;
}
return lo;
}
复杂度：无重复前提下时间 O(log n)，额外空间 O(1)。
易错边界：若允许重复，a[mid]=a[hi] 时无法判断方向，通常只能 hi--，最坏退化为 O(n)；本题无重复，所以不能把两种口径混写。
b_41_10；PDF 第 43 页 · b_43_3；PDF 第 43 页 · b_43_5；PDF 第 43 页 · b_43_7值域映射：空间换时间必须先算下标¶
什么时候能把散列表直接写成数组？¶
何时用：整数值域 [L,R] 有明确且可承受的范围，需要统计出现次数、判重或按值输出。
思路步骤：
- 先算值域大小 M=R-L+1，而不是看元素个数 n。
- 用下标 x-L 表示原值 x；访问前验证 L≤x≤R。
- 初始化 count/seen，再单次扫描更新。
- 若 M 远大于 n，改用真正的哈希表、排序或其他方法，避免稀疏巨数组。
伪代码/关键模板：
复杂度：扫描时间 O(n)，初始化/按值扫描通常 O(M)，空间 O(M)；只有 M=Θ(n) 时才可简写为空间 O(n)。
易错边界：负数不能直接当数组下标；绝对值映射要小心 INT_MIN；值域端点是否包含会决定数组长度是 R-L 还是 R-L+1。
b_13_0；PDF 第 13 页 · b_13_2；PDF 第 13 页 · b_13_3；PDF 第 14 页 · b_14_02018 最小未出现正整数，如何做到 O(n) 且原地标记？¶
何时用：长度 n 的整数数组，求未出现的最小正整数，允许修改原数组。
思路步骤：
- 答案必在 [1,n+1]；把不在 [1,n] 的值改成 n+1。
- 对每个值 v=|a[i]|，若 1≤v≤n，就把 a[v-1] 置负表示 v 出现。
- 第一个仍为正的位置 i 对应答案 i+1。
- 若 1..n 都出现，答案是 n+1。
伪代码/关键模板：
static int ac_smallest_missing_positive(int a[], int n) {
for (int i = 0; i < n; ++i) {
if (a[i] <= 0 || a[i] > n) a[i] = n + 1;
}
for (int i = 0; i < n; ++i) {
int v = a[i] < 0 ? -a[i] : a[i];
if (v >= 1 && v <= n && a[v - 1] > 0) a[v - 1] = -a[v - 1];
}
for (int i = 0; i < n; ++i) {
if (a[i] > 0) return i + 1;
}
return n + 1;
}
复杂度：时间 O(n)，额外空间 O(1)。新版补充/校订：旧版真题解使用 O(n) 辅助数组，这里补充原地标记版本。
易错边界：先清洗再取绝对值，避免直接对 INT_MIN 取绝对值；该算法会破坏原数组；标记下标是 v-1，不是 v。
b_65_1；PDF 第 66 页 · b_66_6；PDF 第 66 页 · b_66_9；PDF 第 66 页 · b_66_13值域 [2n,3n) 去重输出，偏移量到底加还是减？¶
何时用：n 个整数都落在连续长度 n 的区间 [2n,3n)，要求去重、计数或按值序输出。
思路步骤：
- 值域下界 L=2n，大小 M=n。
- 原值 x 映射到 seen[x-2n]，范围正好是 [0,n)。
- 扫描原数组标记；再按下标 i 从小到大输出 i+2n。
- 重复值只会重复写同一标记，因此自然去重。
伪代码/关键模板：
复杂度：时间 O(n)，空间 O(n)。
易错边界：新版补充/校订：旧版文字处出现 A[i]+2n，是方向错误；其后代码使用 A[i]-2n 才是正确映射。还要防止先算 3n 产生整型溢出，工程实现宜用更宽整数。
b_47_9；PDF 第 48 页 · b_48_4；PDF 第 48 页 · b_48_5；PDF 第 49 页 · b_49_0预处理：把重复工作折叠为一次扫描¶
前缀和怎样把区间和查询降到 O(1)？¶
何时用：同一数组上多次查询连续区间和，或枚举大量区间但不想重复累加。
思路步骤：
- 定义 prefix[0]=0。
- 令 prefix[i+1]=prefix[i]+a[i]，即前 i+1 个元素之和。
- 闭区间 [L,R] 之和为 prefix[R+1]-prefix[L]。
- 用 long long 保存累计和，避免多个 int 相加溢出。
伪代码/关键模板：
static void ac_prefix_sum(const int a[], int n, long long prefix[]) {
prefix[0] = 0;
for (int i = 0; i < n; ++i) prefix[i + 1] = prefix[i] + a[i];
}
static long long ac_range_sum(const long long prefix[], int left, int right) {
return prefix[right + 1] - prefix[left];
}
复杂度：预处理 O(n)、每次查询 O(1)、空间 O(n)。
易错边界：prefix 长度必须是 n+1；[L,R] 要用 R+1；若数组会更新，静态前缀和不再适用，应换树状数组等动态结构。
b_14_2；PDF 第 14 页 · b_14_6；PDF 第 14 页 · b_14_7；PDF 第 15 页 · b_15_2；PDF 第 15 页 · b_15_3前后缀最值何时可以压成常数个变量？¶
何时用：每个位置只依赖“此前/此后的最大值或最小值”，且查询方向固定为一次线性扫描。
思路步骤：
- 先判断依赖方向：依赖 [0,i] 就从左向右；依赖 [i,n-1] 就从右向左。
- 若后续仍需随机访问每个位置的最值，建立 prefix/suffix 数组。
- 若扫描到 i 时只用当前累计最值，直接用一个 max_so_far 或 min_so_far。
- 同时涉及最大与最小时维护两个变量，不要错误假设元素全为正。
伪代码/关键模板：
复杂度：时间 O(n)；数组版空间 O(n)，状态压缩版额外空间 O(1)。
易错边界：必须先用合法元素初始化，不能无条件用 0；若 A[i] 可为负，最大乘积可能来自最小值；只有单向消费状态时才能压缩数组。
b_15_6；PDF 第 15 页 · b_15_7；PDF 第 16 页 · b_16_5；PDF 第 16 页 · b_16_6；PDF 第 16 页 · b_16_72025 后缀最大乘积，为什么必须同时维护最大值与最小值？¶
何时用：对每个 i，在 j≥i 中最大化 A[i]×A[j]，数组含正数、负数和零。
思路步骤：
- 从右向左维护后缀最大值 mx 和后缀最小值 mn。
- 更新到位置 i 后，候选只有 A[i]×mx 与 A[i]×mn。
- 取二者较大者写入 res[i]。
- 乘法用 long long 更稳妥；若题目接口固定 int，要说明可能溢出的前提。
伪代码/关键模板：
static void ac_suffix_mul_max(const int a[], long long res[], int n) {
if (n <= 0) return;
int mx = a[n - 1], mn = a[n - 1];
for (int i = n - 1; i >= 0; --i) {
if (a[i] > mx) mx = a[i];
if (a[i] < mn) mn = a[i];
long long p1 = (long long)a[i] * mx;
long long p2 = (long long)a[i] * mn;
res[i] = p1 > p2 ? p1 : p2;
}
}
复杂度：时间 O(n)，额外空间 O(1)（不计输出数组）。新版补充/校订：旧版暴力解只有两重循环，却误写 O(n³)，正确应为 O(n²)。
易错边界：只维护后缀最大值会漏掉“负×更负”；从右向左时先把 a[i] 纳入 mx/mn，才允许 j=i；n=0 时不能访问 a[n-1]。
b_69_5；PDF 第 70 页 · b_70_10；PDF 第 70 页 · b_70_12；PDF 第 70 页 · b_70_13；PDF 第 71 页 · b_71_2；PDF 第 71 页 · b_71_6；PDF 第 71 页 · b_71_7双指针与滑动窗口：先写不变式，再决定谁移动¶
双指针题的移动规则怎样从不变式推出？¶
何时用：一个或两个有序数组同步扫描、左右夹逼，或维护连续区间时。
思路步骤：
- 先写“已排除部分为什么不可能含答案”，再写移动规则。
- 同向归并时，较小者一旦输出/排除就不会再回来。
- 对撞指针时，根据和偏小/偏大决定移动左端或右端。
- 每轮至少有一个指针严格前进，且每个指针至多走完整个数组。
伪代码/关键模板：
复杂度：若每个指针只单向移动，通常时间 O(n+m)，额外空间 O(1)（不计输出）。
易错边界：双层语法不等于 O(n²)，关键看指针是否回退；没有有序性/单调性时不能凭感觉移动；相等分支必须保证至少一个指针变化。
b_17_0；PDF 第 17 页 · b_17_2；PDF 第 17 页 · b_17_6两个升序数组怎样在线性时间归并？¶
何时用：两个有序数组合并为一个有序数组，或求并集/交集的基础扫描。
思路步骤：
- i、j 指向两个未处理区间的首元素，k 指向输出位置。
- 较小元素是全局剩余最小值，写入输出并移动对应指针。
- 一个数组结束后，把另一个数组剩余部分直接复制。
- 若题目要求去重，在写入前与上一个输出比较。
伪代码/关键模板：
static int ac_merge_sorted(const int a[], int n, const int b[], int m, int out[]) {
int i = 0, j = 0, k = 0;
while (i < n && j < m) {
if (a[i] <= b[j]) out[k++] = a[i++];
else out[k++] = b[j++];
}
while (i < n) out[k++] = a[i++];
while (j < m) out[k++] = b[j++];
return k;
}
复杂度：时间 O(n+m)，输出数组之外额外空间 O(1)；若把输出计入则空间 O(n+m)。
易错边界：主循环退出后不要漏复制尾部；相等时只移动一边会保留两份，相等时同时移动则是去重/交集口径，必须按题意选择。
b_17_9；PDF 第 17 页 · b_17_15；PDF 第 17 页 · b_17_16；PDF 第 18 页 · b_18_1升序数组两数之和，左右指针为何不会漏解？¶
何时用：升序数组中找两个不同位置，使两数之和等于目标 k。
思路步骤：
- left=0、right=n-1，始终只考虑 left<right。
- 当前和等于 k 即成功。
- 当前和小于 k 时，固定 left 的任何更小 right 都更小，故只能 left++。
- 当前和大于 k 时，固定 right 的任何更大 left 都更大，故只能 right--。
伪代码/关键模板：
static int ac_two_sum_sorted(const int a[], int n, int k) {
int left = 0, right = n - 1;
while (left < right) {
long long sum = (long long)a[left] + a[right];
if (sum == k) return 1;
if (sum < k) ++left;
else --right;
}
return 0;
}
复杂度：时间 O(n)，额外空间 O(1)。
易错边界：必须是 left<right，避免同一元素使用两次；加法用更宽类型防溢出；若数组无序，移动规则失去依据。
b_38_5；PDF 第 38 页 · b_38_12；PDF 第 40 页 · b_40_2；PDF 第 40 页 · b_40_3；PDF 第 40 页 · b_40_5两个升序数组的最小绝对差，为什么移动较小者？¶
何时用：分别从两个有序数组各取一个数，使绝对差最小。
思路步骤：
- i、j 从各自起点出发，先更新当前差。
- 若 a[i]<b[j]，保持 a[i] 而增大 b[j] 只会让差更大，因此移动 i。
- 若 a[i]>b[j]，对称地移动 j。
- 相等时最优值为 0，可立即结束。
伪代码/关键模板：
static long long ac_min_abs_distance(const int a[], int n, const int b[], int m) {
if (n <= 0 || m <= 0) return -1;
int i = 0, j = 0;
long long best = 9223372036854775807LL;
while (i < n && j < m) {
long long d = (long long)a[i] - b[j];
if (d < 0) d = -d;
if (d < best) best = d;
if (a[i] < b[j]) ++i;
else if (a[i] > b[j]) ++j;
else return 0;
}
return best;
}
复杂度：时间 O(n+m)，额外空间 O(1)。
易错边界：先转 long long 再做减法/取绝对值；任一数组为空时不存在合法数对；“移动较小者”依赖两个数组升序。
b_37_2；PDF 第 37 页 · b_37_3；PDF 第 38 页 · b_38_0；PDF 第 38 页 · b_38_1；PDF 第 38 页 · b_38_3非负数组统计和不超过 k 的连续子数组，窗口不变式是什么？¶
何时用：数组元素非负，统计或寻找满足区间和上界的连续子数组。
思路步骤：
- right 每次纳入一个新元素并更新 sum。
- 当 sum>k 时连续移动 left 并减去离窗元素，直到 sum≤k。
- 此时以 right 结尾、起点在 [left,right] 的区间都合法，共 right-left+1 个。
- 把该数加入答案，再扩展 right。
伪代码/关键模板：
static long long ac_count_nonnegative_windows(const int a[], int n, long long k) {
int left = 0;
long long sum = 0, count = 0;
for (int right = 0; right < n; ++right) {
sum += a[right];
while (left <= right && sum > k) sum -= a[left++];
if (sum <= k) count += right - left + 1;
}
return count;
}
复杂度：left、right 各至多移动 n 次，时间 O(n)，额外空间 O(1)。
易错边界：非负性是关键；出现负数时，缩小窗口不再保证和单调下降。答案可能达到 n(n+1)/2，应用 long long。
b_43_9；PDF 第 43 页 · b_43_10；PDF 第 44 页 · b_44_7；PDF 第 44 页 · b_44_8；PDF 第 44 页 · b_44_10；PDF 第 45 页 · b_45_0统考真题路线：把方法识别落实到得分点¶
2010 数组循环左移，三次逆置怎样记？¶
何时用：将长度 n 的数组左移 p 位，要求时间 O(n)、额外空间 O(1)。
思路步骤：
- 把数组写成 XY，其中 |X|=p、|Y|=n-p，目标是 YX。
- 先逆置 X 得 XᴿY。
- 再逆置 Y 得 XᴿYᴿ。
- 最后逆置整体，得到 (XᴿYᴿ)ᴿ=YX。
伪代码/关键模板：
static void ac_reverse_range(int a[], int lo, int hi) {
while (lo < hi) ac_swap(&a[lo++], &a[hi--]);
}
static void ac_rotate_left(int a[], int n, int p) {
if (n <= 0) return;
p %= n;
if (p < 0) p += n;
if (p == 0) return;
ac_reverse_range(a, 0, p - 1);
ac_reverse_range(a, p, n - 1);
ac_reverse_range(a, 0, n - 1);
}
复杂度：时间 O(n)，额外空间 O(1)。
易错边界：先把 p 归一化到 [0,n)；p=0 时第一段会成为空区间；三次逆置的区间端点不能混用闭/开区间。
b_55_8；PDF 第 55 页 · b_55_9；PDF 第 56 页 · b_56_0；PDF 第 56 页 · b_56_1；PDF 第 56 页 · b_56_3；PDF 第 56 页 · b_56_42011 两个等长升序数组的中位数，怎样每轮丢掉同样多的元素？¶
何时用：两个长度相等的升序数组，求合并后 2n 个元素的下中位数，要求 O(log n) 时间、O(1) 空间。
思路步骤：
- 分别取两个候选区间的中点 m1、m2。
- 中点值相等即可返回。
- a[m1]<b[m2] 时，丢弃 A 的较小前段和 B 的较大后段；反之对称。
- 奇偶长度不同会影响是否保留中点，必须保证两边每轮丢弃元素数相同。
伪代码/关键模板：
static int ac_two_array_lower_median(const int a[], const int b[], int n) {
int s1 = 0, d1 = n - 1, s2 = 0, d2 = n - 1;
while (s1 != d1 || s2 != d2) {
int m1 = s1 + (d1 - s1) / 2;
int m2 = s2 + (d2 - s2) / 2;
if (a[m1] == b[m2]) return a[m1];
int even = ((d1 - s1 + 1) % 2 == 0);
if (a[m1] < b[m2]) {
s1 = even ? m1 + 1 : m1;
d2 = m2;
} else {
d1 = m1;
s2 = even ? m2 + 1 : m2;
}
}
return a[s1] < b[s2] ? a[s1] : b[s2];
}
复杂度：时间 O(log n)，额外空间 O(1)。
易错边界：这里“中位数”按真题口径取第 n 小，不是两个中间数的平均值；n 必须大于 0；每轮两边删去的候选数量必须相等。
b_56_6；PDF 第 56 页 · b_56_7；PDF 第 58 页 · b_58_8；PDF 第 58 页 · b_58_9；PDF 第 58 页 · b_58_10；PDF 第 59 页 · b_59_02013 主元素，摩尔投票为什么还必须二次验证？¶
何时用：寻找出现次数严格超过 n/2 的元素，要求 O(n) 时间、O(1) 空间。
思路步骤：
- count=0 时，把当前元素设为候选并令 count=1。
- 后续元素等于候选就加一，否则减一，表示异值成对抵消。
- 若主元素存在，最终候选必是它。
- 但不存在主元素时也会留下候选，所以必须第二遍计数并验证次数>n/2。
伪代码/关键模板：
static int ac_majority(const int a[], int n, int *value) {
if (n <= 0 || value == NULL) return 0;
int candidate = 0, count = 0;
for (int i = 0; i < n; ++i) {
if (count == 0) {
candidate = a[i];
count = 1;
} else if (a[i] == candidate) {
++count;
} else {
--count;
}
}
int occurrences = 0;
for (int i = 0; i < n; ++i) {
if (a[i] == candidate) ++occurrences;
}
if (occurrences <= n / 2) return 0;
*value = candidate;
return 1;
}
复杂度：两次线性扫描，时间 O(n)，额外空间 O(1)。
易错边界：严格超过一半，不是大于等于。新版补充/校订：旧版的负计数重置写法改为规范的 count==0 重置；不能省略验证遍。
b_59_2；PDF 第 59 页 · b_59_3；PDF 第 61 页 · b_61_9；PDF 第 61 页 · b_61_10；PDF 第 61 页 · b_61_11；PDF 第 62 页 · b_62_42016 集合等分，为什么只定位分界秩就够了？¶
何时用：正整数集合分成大小尽量接近的两组，并让两组和之差尽量大。
思路步骤：
- 个数差最小时，两组大小应为 floor(n/2) 与 ceil(n/2)。
- 为最大化和差，让较小的 floor(n/2) 个元素在一组，其余较大元素在另一组。
- 不需要两组内部有序，只需 Quickselect 把第 floor(n/2) 小的分界放到位。
- 扫描两段求和或直接输出分组。
伪代码/关键模板：
复杂度：随机/平均时间期望 O(n)，固定坏枢轴最坏 O(n²)；迭代版额外空间 O(1)。新版补充/校订：旧版题目问“平均复杂度”，应明确写期望/平均而非无条件 O(n)。
易错边界：n 为奇数时较大元素一组应多一个；集合若允许重复，划分位置仍有效但内部顺序不定；不要为输出两个集合而误做完整排序。
b_62_5；PDF 第 62 页 · b_62_6；PDF 第 63 页 · b_63_2；PDF 第 63 页 · b_63_3；PDF 第 64 页 · b_64_10；PDF 第 64 页 · b_64_11；PDF 第 65 页 · b_65_02020 三数组最小距离，为什么只移动当前最小值？¶
何时用：三个升序数组各取一个数，最小化 |a-b|+|b-c|+|c-a|。
思路步骤：
- 利用恒等式 D=2×(当前最大值-当前最小值)。
- 三个指针从起点出发，更新当前 D。
- 若不移动最小值，仅增大中间值或最大值，当前跨度不可能缩小。
- 因此只移动指向当前最小值的指针；任一数组耗尽即结束。
伪代码/关键模板：
static long long ac_three_array_min_distance(
const int a[], int n, const int b[], int m, const int c[], int k
) {
if (n <= 0 || m <= 0 || k <= 0) return -1;
int i = 0, j = 0, t = 0;
long long best = 9223372036854775807LL;
while (i < n && j < m && t < k) {
int mn = a[i], mx = a[i];
if (b[j] < mn) mn = b[j];
if (c[t] < mn) mn = c[t];
if (b[j] > mx) mx = b[j];
if (c[t] > mx) mx = c[t];
long long d = 2LL * ((long long)mx - mn);
if (d < best) best = d;
if (a[i] <= b[j] && a[i] <= c[t]) ++i;
else if (b[j] <= a[i] && b[j] <= c[t]) ++j;
else ++t;
}
return best;
}
复杂度：三个指针各至多走一遍，时间 O(n+m+k)，额外空间 O(1)。
易错边界：三个集合必须非空且升序；相等最小值时移动任一最小指针都安全，但必须保证推进；用更宽整数计算两倍跨度。
b_67_0；PDF 第 67 页 · b_67_1；PDF 第 68 页 · b_68_7；PDF 第 69 页 · b_69_0；PDF 第 69 页 · b_69_2；PDF 第 69 页 · b_69_3；PDF 第 69 页 · b_69_4