顺序表-递增有序表合并
两个递增有序表合并操作
题目：
将两个递增有序的顺序表 A 和 B 合并成一个新的递增有序顺序表 C。
思路：
- 使用三个索引
i,j,k分别遍历顺序表A,B和合并后的顺序表C。 - 比较
A和B当前索引指向的元素，将较小的元素放入C中，并移动对应的索引。 - 当
A或B的元素全部放入C后，将剩余的元素直接复制到C中。
整体代码：
// 函数声明，用于合并两个递增有序顺序表A和B到顺序表C中
bool merge(Sqlist A, Sqlist B, Sqlist &C) {int i = 0, j = 0, k = 0; // 初始化索引i, j, k为0，分别用于A, B和C// 合并两个有序表的元素到C中while (i < A.length && j < B.length) { // 当A和B都还有元素时if (A.data[i] < B.data[j]) { // 如果A的当前元素小于B的当前元素C.data[k++] = A.data[i++]; // 将A的元素放入C，并移动A和C的索引} else {C.data[k++] = B.data[j++]; // 将B的元素放入C，并移动B和C的索引}}// 将A中剩余的元素复制到C中while (i < A.length) {C.data[k++] = A.data[i++];}// 将B中剩余的元素复制到C中while (j < B.length) {C.data[k++] = B.data[j++];}C.length = k; // 更新C的长度为合并后的元素数量return true; // 返回成功标志
}
题目：
尽可能高效找出数组中未出现的最小正整数。
思路：
- 初始化辅助数组：创建一个大小为
n的辅助数组B，用于标记数组A中出现的正整数。 - 标记出现的正整数：遍历数组
A，对于每个正整数A[i]，如果A[i]在1到n之间，则将B[A[i] - 1]标记为1。 - 查找未出现的最小正整数：再次遍历辅助数组
B，找到第一个值为0的位置，该位置即为未出现的最小正整数。 - 释放辅助数组：删除辅助数组
B。
整体代码：
int find(int A[], int n) {// 1. 初始化辅助数组 B，大小为 nint *B = new int[n]; // 创建大小为 n 的辅助数组 B// 2. 遍历数组 A，标记出现的正整数for (int k = 0; k < n; ++k) {B[k] = 0; // 初始化 B 数组，标记未出现的正整数}for (int i = 0; i < n; ++i) {if (A[i] > 0 && A[i] <= n) {B[A[i] - 1] = 1; // 标记 A[i] 出现，B[A[i] - 1] 为 1}}// 3. 查找未出现的最小正整数for (int i = 0; i < n; ++i) {if (B[i] == 0) {break; // 找到第一个未出现的正整数，退出循环}}// 4. 释放辅助数组 Bdelete[] B; // 释放辅助数组 B 的内存// 返回未出现的最小正整数return i + 1; // 返回未出现的最小正整数
}
说明：
- 辅助数组 B：用于标记数组
A中出现的正整数。 - 标记出现的正整数：遍历数组
A，对于每个正整数A[i]，如果A[i]在1到n之间，则将B[A[i] - 1]标记为1。 - 查找未出现的最小正整数：再次遍历辅助数组
B，找到第一个值为0的位置，该位置即为未出现的最小正整数。 - 释放辅助数组：删除辅助数组
B，释放内存。