1. 顺序表

本资料共 11 道顺序表代码题。核心是明确下标含义、容量上限和循环不变量：筛选题通常让 i 负责读取、k 负责写入；区间题统一采用闭区间；所有访问都必须先证明下标合法。

1.0 统一定义与约定

以下代码采用 C++ 引用语法；数组下标从 0 开始，合法数据区为 data[0..length-1]。

constexpr int MAXSIZE = 100;
using ElemType = int;

struct SqList {
    ElemType data[MAXSIZE];
    int length = 0;
};

• 涉及插入或合并时必须检查容量，不能写入 data[MAXSIZE]。
• 需要返回元素且可能失败时，使用 bool 表示成功与否，用引用参数带回结果，避免用某个合法整数充当失败哨兵。
• 除非特别说明，“递增”按非递减理解，即允许相等关键字。

---

1.1 代码题 1：递增有序表插入元素

题目

在非递减顺序表中插入元素 x，使插入后仍保持非递减。

bool OrderedInsert(SqList &L, ElemType x) {
    if (L.length >= MAXSIZE) return false;

    int pos = 0;
    // 跳过所有 <= x 的元素，使 x 插到已有相等元素之后。
    while (pos < L.length && L.data[pos] <= x) ++pos;

    for (int j = L.length; j > pos; --j)
        L.data[j] = L.data[j - 1];

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

• 循环结束时，[0,pos) 中元素均不大于 x，[pos,length) 中元素均大于 x。
• 从尾部向前移动，避免尚未复制的元素被覆盖。
• 时间 $O(n)$、空间 $O(1)$；插在已有相等元素之后可保持稳定性。
• 原 PDF 使用了未定义变量 index，且比较方向不能正确找到插入点；上面已修正。

---

1.2 代码题 2：用末元素覆盖最小元素

题目

删除顺序表中的最小元素，用最后一个元素填补其位置，并返回被删除的最小值。

bool DeleteMin(SqList &L, ElemType &minValue) {
    if (L.length == 0) return false;

    int minIndex = 0;
    for (int i = 1; i < L.length; ++i)
        if (L.data[i] < L.data[minIndex])
            minIndex = i;

    minValue = L.data[minIndex];
    L.data[minIndex] = L.data[L.length - 1];
    --L.length;
    return true;
}

• 时间 $O(n)$、空间 $O(1)$。
• 题目明确要求“末元素覆盖”，因此删除后不保证原有次序；若必须保持次序，应把后继元素依次前移。
• 空表时不能读取 data[0]，所以必须先判空。

---

1.3 代码题 3：原地逆置顺序表

void Reverse(SqList &L) {
    for (int i = 0, j = L.length - 1; i < j; ++i, --j) {
        ElemType temp = L.data[i];
        L.data[i] = L.data[j];
        L.data[j] = temp;
    }
}

• 循环不变量：i 左侧和 j 右侧的元素已经到达最终位置。
• 奇数长度时中间元素无须处理；空表时 j=-1，条件 i<j 直接为假。
• 时间 $O(n)$、空间 $O(1)$。

---

1.4 代码题 4：交换两个连续子序列

题目

将

$$ (a_1,a_2,\ldots,a_m,b_1,b_2,\ldots,b_n) $$

原地变为

$$ (b_1,b_2,\ldots,b_n,a_1,a_2,\ldots,a_m) $$

void ReverseRange(SqList &L, int left, int right) { // 闭区间
    while (left < right) {
        ElemType temp = L.data[left];
        L.data[left++] = L.data[right];
        L.data[right--] = temp;
    }
}

bool ExchangeBlocks(SqList &L, int m, int n) {
    if (m < 0 || n < 0 || m + n != L.length) return false;

    ReverseRange(L, 0, m - 1);
    ReverseRange(L, m, m + n - 1);
    ReverseRange(L, 0, m + n - 1);
    return true;
}

• 三次逆置的中间状态为 $A^RB^R\rightarrow( A^RB^R)^R=BA$。
• m、n 是两个子序列的长度，所以第二段末下标是 m+n-1，不是 n-1；原 PDF 在此混淆了长度与下标。
• 本题交换的是构成整个顺序表的两个连续块，因此还必须满足 m+n==L.length。若只想交换表的某个前缀，应另行传入区间边界并在接口名中说明。
• 时间 $O(m+n)$、空间 $O(1)$。

---

1.5 代码题 5：删除所有值为 x 的元素

方法一：写指针保存保留元素

void DeleteX(SqList &L, ElemType x) {
    int k = 0; // 下一次写入位置
    for (int i = 0; i < L.length; ++i)
        if (L.data[i] != x)
            L.data[k++] = L.data[i];
    L.length = k;
}

方法二：累计已删除数量

void DeleteXByCount(SqList &L, ElemType x) {
    int removed = 0;
    for (int i = 0; i < L.length; ++i) {
        if (L.data[i] == x)
            ++removed;
        else
            L.data[i - removed] = L.data[i];
    }
    L.length -= removed;
}

• 两种方法都保持剩余元素的相对次序，时间 $O(n)$、空间 $O(1)$。
• 不要每发现一个 x 就把全部后继前移，否则最坏时间会变成 $O(n^2)$。

---

1.6 代码题 6：删除值在闭区间 s 到 t 内的元素

bool DeleteRange(SqList &L, ElemType s, ElemType t) {
    if (s > t) return false;

    int k = 0;
    for (int i = 0; i < L.length; ++i)
        if (L.data[i] < s || L.data[i] > t)
            L.data[k++] = L.data[i];
    L.length = k;
    return true;
}

• 保留条件是区间补集 value < s || value > t；把 || 错写成 && 会导致没有元素能被保留。
• s>t 属于非法区间，本实现返回 false 且不修改顺序表。
• 时间 $O(n)$、空间 $O(1)$。

---

1.7 代码题 7：有序表原地去重

void DeleteDuplicates(SqList &L) { // L 已非递减有序
    if (L.length <= 1) return;

    int k = 0; // 最后一个已保留元素的下标
    for (int i = 1; i < L.length; ++i)
        if (L.data[i] != L.data[k])
            L.data[++k] = L.data[i];
    L.length = k + 1;
}

• k 指向最后一个已保留元素，而不是下一写入位置，所以最终长度是 k+1。
• 有序性保证相同元素连续；无序表不能直接使用本算法。
• 时间 $O(n)$、空间 $O(1)$，且保留每个值第一次出现的记录。

---

1.8 代码题 8：合并两个递增顺序表

bool Merge(const SqList &A, const SqList &B, SqList &C) {
    if (A.length + B.length > MAXSIZE) return false;

    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;
    return true;
}

• A、B 必须已按同一规则有序，且输出表 C 不能与输入表共用同一存储区。
• 相等时先取 A 中记录可保持两输入序列之间的稳定次序。
• 一方耗尽后，另一方剩余元素直接复制；时间 $O(m+n)$，输出空间 $O(m+n)$。
• 原 PDF 的返回类型、变量名和 l.length 均不一致，且缺少容量检查；上面已统一。

---

1.9 代码题 9：两个递增序列合并后的中位数

本题必须先确认“中位数”的口径。以下按总长度 $N=m+n$ 的下中位数处理，其 0 下标为：

$$ target=\left\lfloor\frac{N-1}{2}\right\rfloor $$

方法一：完整合并

bool LowerMedianByMerge(const SqList &A, const SqList &B,
                        ElemType &median) {
    SqList C;
    if (!Merge(A, B, C) || C.length == 0) return false;
    median = C.data[(C.length - 1) / 2];
    return true;
}

方法二：只归并到目标位置

bool LowerMedian(const SqList &A, const SqList &B,
                 ElemType &median) {
    const int total = A.length + B.length;
    if (total == 0) return false;

    const int target = (total - 1) / 2;
    int i = 0, j = 0;
    for (int k = 0; k <= target; ++k) {
        if (j >= B.length ||
            (i < A.length && A.data[i] <= B.data[j]))
            median = A.data[i++];
        else
            median = B.data[j++];
    }
    return true;
}

• 方法一时间 $O(m+n)$、另需 $O(m+n)$ 输出空间；方法二最坏时间 $O(m+n)$、额外空间 $O(1)$。
• 原 PDF 的 GetMid 返回了中位数下标，不是该下标处的元素，属于实质性错误。
• 若题目定义上中位数或偶数长度取两中间值平均数，应相应改变目标下标和返回类型。

---

1.10 代码题 10：最小未出现正整数

关键结论

长度为 $n$ 的数组中，最小未出现正整数一定属于 $[1,n+1]$。大于 $n$ 的值、0 和负数都不会影响答案。

int FirstMissingPositive(const int A[], int n) {
    bool *seen = new bool[n + 1]{}; // 只使用 seen[1..n]

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

    int answer = 1;
    while (answer <= n && seen[answer]) ++answer;

    delete[] seen;
    return answer;
}

• 时间 $O(n)$、空间 $O(n)$；若 1..n 全出现，循环自然返回 n+1。
• 记录数组必须零初始化，映射前必须检查 1<=A[i]<=n，否则会越界。
• 原 PDF 在寻找答案时扫描了原数组 a 而非标记数组 record，还混用了 minNumber、maxNumber 与大小写不同的释放变量；上面已全部修正。

---

1.11 代码题 11：寻找主元素

题目

若某元素出现次数严格大于 $n/2$，称为主元素。找到它；不存在则报告失败。

最优空间：Boyer-Moore 投票并复核

bool MajorityElement(const int A[], int n, int &majority) {
    if (n <= 0) return false;

    int candidate = A[0];
    int votes = 1;
    for (int i = 1; i < n; ++i) {
        if (votes == 0) {
            candidate = A[i];
            votes = 1;
        } else if (A[i] == candidate) {
            ++votes;
        } else {
            --votes;
        }
    }

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

    if (count <= n / 2) return false;
    majority = candidate;
    return true;
}

• 两个不同元素可以成对抵消；若主元素存在，抵消后它必是候选者。
• “候选者”不等于“必然是主元素”，所以第二趟必须统计并验证 count>n/2。
• 时间 $O(n)$、空间 $O(1)$。
• 原 PDF 利用 0<a_i<n 建立计数数组也能做到 $O(n)$ 时间，但需要 $O(n)$ 空间，且依赖值域前提；投票法不依赖值域。

---

1.12 原 PDF 代码错误清单

相关知识

• 科目导航：数据结构导航
• 阅读顺序：上一篇：重点算法汇总 · 下一篇：链表代码
• 关联专题：顺序表原理

1.13 本节复盘

• 插入：先检查容量，找位置后必须从后向前搬移。
• 压缩删除：i 读、k 写；去重时先判断 k 表示“下一写入位置”还是“最后保留位置”。
• 交换相邻块：三个闭区间依次逆置，长度不能误当下标。
• 有序表合并：三指针、复制剩余段、相等时固定取值侧，并检查输出容量。
• 中位数函数必须返回元素而不是下标；题目未说明时要先明确下中位数、上中位数或平均值口径。
• 标记数组题先证明答案范围再映射；主元素题必须验证候选者。