一、顺序表（15 题）
一、顺序表（15 题）¶
默认结构¶
1. 递增有序顺序表插入元素 x，插入后仍递增有序¶
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;
}
复杂度： 时间 O(n)，额外空间 O(1)。
核心思路： 先找到第一个大于 x 的元素位置，再从表尾向后搬移元素，最后插入 x 并更新表长。
2. 用表尾元素覆盖第一个最小元素，并返回最小值¶
若有多个最小值，选择第一次出现的位置；若表尾元素就是所选最小元素，则不改变顺序表。
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;
}
复杂度： 时间 O(n)，额外空间 O(1)。
校订注：题面只要求“覆盖”并强调表尾为最小值时状态不变，因此这里不缩短表长。若题目本意是“删除最小元素并以表尾填补”，则覆盖后还应执行
L->length--，且即使最小元素在表尾也应缩短表长。
3. 数组循环左移 p 个位置（2010 年统考题）¶
将 (X0, X1, ..., Xn-1) 变为 (Xp, Xp+1, ..., Xn-1, X0, ..., Xp-1)，其中 0 < p < n。
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);
}
复杂度： 时间 O(n)，额外空间 O(1)。
核心思路： 先整体逆置，再分别逆置前 n-p 个元素和后 p 个元素。
4. 无序顺序表去重，仅保留第一次出现的元素¶
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;
}
}
复杂度： 时间 O(n²)，额外空间 O(1)。
核心思路： 固定每个第一次出现的元素，将它后面与之不同的元素依次前移，从而覆盖其重复项。
5. 有序顺序表去重，仅保留第一次出现的元素¶
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;
}
复杂度： 时间 O(n)，额外空间 O(1)。
核心思路： k 始终指向下一个唯一元素应写入的位置；有序表中的重复值必然相邻。
6. 在有序表中找出出现次数最多的元素及次数¶
若有多个众数，优先选择值最小的元素。
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;
}
复杂度： 时间 O(n)，额外空间 O(1)。
校订注：原稿未初始化
max_val，当所有元素只出现一次时会产生未定义结果。本版将第一个元素设为初始众数；只在次数严格更大时更新，因此并列时自然保留较小值。
7. 找出数组中的主元素（2013 年统考题）¶
数组元素满足 0 <= A[i] < n。若某元素出现次数超过 n/2，则为主元素；不存在时返回 -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;
}
复杂度： 时间 O(n)，额外空间 O(n)。
核心思路： 利用元素取值范围建立计数数组，再查找计数超过 n/2 的值。
8. 找出数组中未出现的最小正整数（2018 年统考题）¶
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;
}
复杂度： 时间 O(n)，额外空间 O(n)。
核心思路： 答案只可能位于 [1, n+1]。标记 1..n 是否出现，再返回第一个未被标记的数。
9. 两个递增有序表合并为一个递增有序表¶
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;
}
复杂度： 时间 O(m+n)；除结果表外，额外空间 O(1)。
10. 两个递增有序表合并为一个递减有序表¶
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;
}
复杂度： 时间 O(m+n)；除结果表外，额外空间 O(1)。
11. 输出三个递增无重复序列的公共元素¶
三个序列 A、B、C 长度均为 n。
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++;
}
}
}
复杂度： 时间 O(n)，额外空间 O(1)。
核心思路： 三指针同步前进；三值相等时输出，否则让所有小于当前最大值的指针前移。
校订注：原稿的
fmax使用严格比较，在最大值并列时可能返回较小值，本版已修正。
12. 三个升序集合的最小三元组距离（2020 年统考题）¶
三元组距离为 D = |a-b| + |b-c| + |c-a|。
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;
}
复杂度： 时间 O(m+n+p)，额外空间 O(1)。
核心思路： 每次计算当前三元组的距离，然后移动三者中最小值所在的指针；只有提高最小值才可能缩小极差和距离。
暴力法需枚举所有三元组，时间复杂度为 O(mnp)。原稿暴力代码末尾误写为 return min_val;，正确变量应为 min_dis。
13. 两个等长升序序列的中位数（2011 年统考题）¶
这里的中位数指合并后 2n 个元素中的第 n 小元素，即较小的那个中间数。
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];
}
复杂度： 时间 O(log n)，额外空间 O(1)。
校订注：原稿采用完整归并，复杂度为时间
O(n)、空间O(n)，不满足题目“时间和空间都尽可能高效”的要求。本版换为等长区间折半法。
14. 将负数移到数组前端，非负数移到后端¶
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;
}
}
}
复杂度： 时间 O(n)，额外空间 O(1)。
核心思路： 左指针寻找非负数，右指针寻找负数，二者交换后继续向中间收缩。此算法不保证原相对次序稳定。
15. 计算 res[i] = max(A[i] * A[j])（2025 年统考题）¶
其中 0 <= i <= j <= n-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;
}
}
复杂度： 时间 O(n)，除输出数组外额外空间 O(1)。
核心思路： 从右向左维护后缀最大值和最小值。A[i] 非负时与后缀最大值相乘最优；为负时与后缀最小值相乘最优。更新后缀极值时包含 A[i]，因此也覆盖 j=i 的情况。