欢迎各位彦祖与热巴畅游本人专栏与博客
你的三连是我最大的动力
以下图片仅代表专栏特色 [点击箭头指向的专栏名即可闪现]
专栏跑道一
➡️网络空间安全——全栈前沿技术持续深入学习
编辑
专栏跑道二
➡️ 24 Network Security -LJS
编辑
编辑
编辑
专栏跑道三
➡️ MYSQL REDIS Advance operation
编辑
专栏跑道四
➡️HCIP；H3C-SE;CCIP——LJS[华为、华三、思科高级网络]
编辑
专栏跑道五
➡️RHCE-LJS[Linux高端骚操作实战篇]
专栏跑道六
➡️数据结构与算法[考研+实际工作应用+C程序设计]
编辑
专栏跑道七
➡️RHCSA-LJS[Linux初级及进阶骚技能]
编辑
上节回顾
课后习题精选：
（13）：给定一个含n个整数的数组Q,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数
编辑
解题思路
>定义标记数组 >记录A中出现正整数情况
具体代码实现：
#include <iostream> #include <string.h> using namespace std; #define Maxsize 50 // 定义顺序表结构 typedef struct { int data[Maxsize]; // 存储顺序表中的数据 int length = 0; // 当前顺序表的长度 } SqList; // 插入测试数据函数 void ListInsert(SqList &L) { int val = 0; // 从标准输入读取整数 while (cin >> val) { // 将输入值存储到顺序表中，并更新长度 L.data[L.length++] = val; // 判断是否为输入行的结束符（回车），若是则停止读取 if (cin.get() == '\n') { break; } } } // 打印顺序表函数 void PrintList(SqList L) { for (int i = 0; i < L.length; i++) { // 打印顺序表中的每个元素，以制表符分隔 cout << L.data[i] << '\t'; } cout << endl; // 打印换行符 } // 找到1到n范围内的最小缺失正整数 int FindMin(SqList &L, int n) { int i; // 动态分配一个大小为n的数组B int *B = new int[n]; // 将数组B初始化为0 memset(B, 0, sizeof(int) * n); // 遍历顺序表中的数据 for (i = 0; i < n; i++) { // 若数据在1到n范围内，则在数组B中对应位置标记为1 if (L.data[i] > 0 && L.data[i] <= n) { B[L.data[i] - 1] = 1; } } // 查找数组B中第一个未被标记的位置 for (i = 0; i < n; i++) { if (B[i] == 0) { break; } } // 返回缺失的最小正整数 return i + 1; } int main() { SqList L; // 创建一个顺序表 ListInsert(L); // 从输入中插入测试数据 // 查找并打印1到5范围内的最小缺失正整数 cout << FindMin(L, 5); }
（12）：已知一个整数序列A=（a0,a1,an-1），其中若存在则称x为A的主元素。
编辑
解题思路：
>算法关键就是扫描数组 >标记处一个可能成为主元的元素，然后重新计数
具体代码实现：
#include <iostream> using namespace std; #define Maxsize 50 // 定义顺序表结构 typedef struct { int data[Maxsize]; // 存储顺序表中的数据 int length = 0; // 当前顺序表的长度 } SqList; // 插入测试数据 void ListInsert(SqList &L) { int val = 0; // 从标准输入读取整数 while (cin >> val) { // 将输入值存储到顺序表中，并更新长度 L.data[L.length++] = val; // 判断是否为输入行的结束符（回车），若是则停止读取 if (cin.get() == '\n') { break; } } } // 打印顺序表 void PrintList(SqList L) { for (int i = 0; i < L.length; i++) { // 打印顺序表中的每个元素，以制表符分隔 cout << L.data[i] << '\t'; } cout << endl; // 打印换行符 } // 查找出现次数超过一半的元素 int MainValue(SqList &L, int n) { int i, c, count = 1; c = L.data[0]; // 初始候选元素为第一个元素 // 遍历顺序表中的数据，确定可能的多数元素 for (i = 1; i < n; i++) { if (L.data[i] == c) { count++; // 如果当前元素等于候选元素，则计数器加1 } else { if (count > 0) { count--; // 如果当前元素与候选元素不同且计数器大于0，则计数器减1 } else { c = L.data[i]; // 选择新的候选元素 count = 1; // 重置计数器为1 } } } // 再次遍历确认候选元素是否真的出现次数超过一半 if (count > 0) { for (i = count = 0; i < n; i++) { if (L.data[i] == c) { count++; // 统计候选元素的实际出现次数 } } } // 如果候选元素的出现次数超过一半，则返回该元素，否则返回-1 if (count > n / 2) { return c; } else { return -1; } } int main() { SqList L; // 创建一个顺序表 ListInsert(L); // 从输入中插入测试数据 // 查找并打印出现次数超过一半的元素 cout << MainValue(L, 5); }
（11）：一个长度为L的升序序列S，处在第L/2个位置的数称为S的中位数，例如，若序列则S1的中位数是15，两个序列的中位数是11，现在有两个等长升序A和B
编辑
解题思路
>分成3种情况，相等、小于、大于 >等于直接返回 >小于、大于分别减半
具体代码实现
#include <iostream> using namespace std; #define Maxsize 50 // 定义顺序表结构 typedef struct { int data[Maxsize]; // 存储数据的数组 int length = 0; // 顺序表的当前长度 } SqList; // 插入测试数据 void ListInsert(SqList &L) { int val = 0; while (cin >> val) // 从标准输入读取数据 { L.data[L.length++] = val; // 将读取的值插入顺序表，并增加长度 if (cin.get() == '\n') // 检测到换行符，结束输入 { break; } } } // 打印顺序表 void PrintList(SqList L) { for (int i = 0; i < L.length; i++) { cout << L.data[i] << '\t'; // 打印顺序表中的每个元素 } cout << endl; } // 题目功能函数：查找两个排序数组中的中位数 int SearchMid(SqList &L1, SqList &L2, int n) { int s1 = 0, d1 = n - 1; // L1 的开始和结束下标 int m1, s2 = 0, d2 = n - 1; // L2 的开始和结束下标 int m2; while (s1 != d1 || s2 != d2) // 当两个数组还没有缩小到只有一个元素时 { m1 = (s1 + d1) / 2; // L1 的中间下标 m2 = (s2 + d2) / 2; // L2 的中间下标 if (L1.data[m1] == L2.data[m2]) // 如果中间元素相等，则找到中位数 { return L1.data[m1]; } if (L1.data[m1] < L2.data[m2]) // 如果 L1 中的中间元素小于 L2 中的中间元素 { if ((s1 + d1) % 2 == 0) // 如果 L1 的当前区间大小为偶数 { s1 = m1; // 将 L1 的起始位置更新为 m1 d2 = m2; // 将 L2 的结束位置更新为 m2 } else // 如果 L1 的当前区间大小为奇数 { s1 = m1 + 1; // 将 L1 的起始位置更新为 m1 + 1 d2 = m2; // 将 L2 的结束位置更新为 m2 } } else // 如果 L1 中的中间元素大于 L2 中的中间元素 { if ((s2 + d2) % 2 == 0) // 如果 L2 的当前区间大小为偶数 { d1 = m1; // 将 L1 的结束位置更新为 m1 s2 = m2; // 将 L2 的起始位置更新为 m2 } else // 如果 L2 的当前区间大小为奇数 { d1 = m1; // 将 L1 的结束位置更新为 m1 s2 = m2 + 1; // 将 L2 的起始位置更新为 m2 + 1 } } } // 返回最终中位数，取两个数组中当前位置的较小值 return L1.data[s1] < L2.data[s2] ? L1.data[s1] : L2.data[s2]; } int main() { SqList L1, L2; // 创建两个顺序表 ListInsert(L1); // 插入测试数据到 L1 ListInsert(L2); // 插入测试数据到 L2 cout << SearchMid(L1, L2, 5); // 输出两个排序数组中位数 }
（10） ：一个长度为L的升序序列S，处在第L/2个位置的数称为S的中位数，例如，若序列则S1的中位数是15，两个序列的中位数是11，现在有两个等长升序A和B
编辑
解题思路：
>将子数组逆转3次
具体代码实现：
#include <iostream> using namespace std; #define Maxsize 50 // 定义顺序表结构 typedef struct { int data[Maxsize]; // 存储顺序表中的数据 int length = 0; // 当前顺序表的长度 } SqList; // 插入测试数据 void ListInsert(SqList &L) { int val = 0; // 从标准输入读取整数 while (cin >> val) { // 将输入值存储到顺序表中，并更新长度 L.data[L.length++] = val; // 判断是否为输入行的结束符（回车），若是则停止读取 if (cin.get() == '\n') { break; } } } // 打印顺序表 void PrintList(SqList L) { for (int i = 0; i < L.length; i++) { // 打印顺序表中的每个元素，以制表符分隔 cout << L.data[i] << '\t'; } cout << endl; // 打印换行符 } // 逆转数组的部分元素 void Reverse(SqList &L, int left, int right) { // 将指定区间 [left, right] 的元素交换以实现逆转 for (int i = 0; i < (right - left + 1) / 2; i++) { int temp = L.data[i + left]; L.data[i + left] = L.data[right - i]; L.data[right - i] = temp; } } // 逆转顺序表的两部分以及整个数组 void ReverseList(SqList &L, int p) { // 逆转前 p 个元素 Reverse(L, 0, p - 1); // 逆转从 p 到最后的元素 Reverse(L, p, L.length - 1); // 逆转整个数组 Reverse(L, 0, L.length - 1); } int main() { SqList L; // 创建一个顺序表 ListInsert(L); // 从输入中插入测试数据 // 逆转顺序表中的前 3 个元素，以及从第 3 个元素开始的其余部分，然后逆转整个数组 ReverseList(L, 3); // 打印逆转后的顺序表 PrintList(L); }
,,,
