顺序表-递增有序表合并

两个递增有序表合并操作

题目：

将两个递增有序的顺序表 A 和 B 合并成一个新的递增有序顺序表 C。

思路：

1. 使用三个索引 i, j, k 分别遍历顺序表 A, B 和合并后的顺序表 C。
2. 比较 A 和 B 当前索引指向的元素，将较小的元素放入 C 中，并移动对应的索引。
3. 当 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; // 返回成功标志
}

题目：

尽可能高效找出数组中未出现的最小正整数。

思路：

1. 初始化辅助数组：创建一个大小为 n 的辅助数组 B，用于标记数组 A 中出现的正整数。
2. 标记出现的正整数：遍历数组 A，对于每个正整数 A[i]，如果 A[i] 在 1 到 n 之间，则将 B[A[i] - 1] 标记为 1。
3. 查找未出现的最小正整数：再次遍历辅助数组 B，找到第一个值为 0 的位置，该位置即为未出现的最小正整数。
4. 释放辅助数组：删除辅助数组 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，释放内存。