欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 科技 > 能源 > 顺序表-递增有序表合并

顺序表-递增有序表合并

2025/4/24 16:58:25 来源:https://blog.csdn.net/qq_52291558/article/details/144484604  浏览:    关键词:顺序表-递增有序表合并

两个递增有序表合并操作

题目:

将两个递增有序的顺序表 AB 合并成一个新的递增有序顺序表 C

思路:

  1. 使用三个索引 i, j, k 分别遍历顺序表 A, B 和合并后的顺序表 C
  2. 比较 AB 当前索引指向的元素,将较小的元素放入 C 中,并移动对应的索引。
  3. AB 的元素全部放入 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]1n 之间,则将 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]1n 之间,则将 B[A[i] - 1] 标记为 1
  • 查找未出现的最小正整数:再次遍历辅助数组 B,找到第一个值为 0 的位置,该位置即为未出现的最小正整数。
  • 释放辅助数组:删除辅助数组 B,释放内存。

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词