2020考研-王道数据结构-线性表-顺序表 淡淡的烟草味﹌ 2022-02-04 10:51 231阅读 0赞 # 注意 # #### 1. 每道题目以函数的形式给出。 #### #### 2. 为了提高代码的可读性，STL库中的有的函数不在重复，比如Reverse、Swap、Sort等函数。 #### #### 3. 语言采用的是C++11标准，所以大家编译调试的需要注意，某些函数C++98的编译器不支持。 #### #### 4. 关于第一张线性表的题目比较简单，数据结构全部采用数组进行模拟。 #### # 第八题 # ##### 题目简介： ##### 将线性表中的前m个元素与线性表中后 n-m 个元素进行交换。 例如对于序列 1 2 3 4 5 6 7，将前4个元素与后3个进行交换，则序列变成 5 6 7 1 2 3 4 ##### 思路描述 ##### 这种题目都有小技巧，如果平时没遇见过，考试的时候多半用了很复杂的逻辑，这样面试官的印象分直接就下来了。 做法就是，先把前 m 个元素逆置，再把后 n - m 个元素逆置，再把整个序列逆置一遍就可以了。大家最好是手动模拟一遍，就知道这个算法的巧妙之处了。 整个算法的**时间复杂度是O(n)** ##### 代码 ##### void swap_A(int A[], int m, int n) { reverse(A, m); // 逆置前m个元素 reverse(A + m, n - m); // 逆置后 n - m 个元素 reverse(A, m + n); // 整个序列逆置一遍 return; } # 第九题 # ##### 题目简介 ##### 找到有序表中值为 x 的元素， 如果找到，则与该元素后面的元素进行交换；如果未找到，则插入该元素使序列仍然有序。 ##### 思路描述 ##### 注意该序列使有序的，所以可以二分查找该元素，**二分查找的复杂度是O(lgn)** 级别的，但是如果没找到的话，还需要把该元素插入，**插入该元素的时间复杂度是O(n)** 级别的。 ##### 代码 ##### void find_A(int A[], int &length, int x) { int l = 0, r = length - 1; // 二分查找， 关于二分算法的学习，可以参考我的二分模板总结的博客 while (l < r){ int mid = (l + r) >> 1; if (A[mid] >= x) r = mid; else l = mid + 1; } // 如果找到该元素 if (A[l] == x) { if (l + 1 == length) return; swap(A[l], A[l + 1]); } else // 如果未找到该元素 { A[length] = x; for (int i = length; i > 0; i--) { if (A[i] < A[i - 1]){ swap(A[i], A[i - 1]); } else break; } length++; // 注意要更新线性表的长度 } } # 第十题 # ##### 题目简介 ##### 将线性表中的前p个元素循环左移p个单位，例如1 2 3 4 5 6 7，循环左移3个单位，则成为4 5 6 7 1 2 3. ##### 思路分析 ##### 其实大家不难看出这就是第八题吗，所以话不多说。大家对于算法一定要多思考，多上机，毕竟计算机是个实践科学。 ##### 代码 ##### void Ror_left(int A[], int length, int p) { // 算法过程完全是模拟的第八题 reverse(A, p); reverse(A + p, length - p); reverse(A, length); } # 第十一题 # ##### 题目简介 ##### 给定两个有序序列，请你设计一个算法找出两个序列的中位数，使时间复杂度和空间复杂度尽可能的低。 例如 序列1：1 2 3 4 5；序列二 8 9 10 11 12。两个序列的中位数应该是 5. ##### 思路分析 ##### 考研的时候，大家不要去死磕复杂度和空间复杂度最优的算法，这样往往得不偿失，就比如这个题目，正常去思考的话，我们可以合成一个有序序列吗，这样的时间复杂度是O(n), 其实也是阔以的。 下面说一个比较优秀的算法，也就是课本给的一个思路: 比较两个序列的中位数：**序列A的中位数是mid\_a, 序列B的中位数是 mid\_b，默认升序排列。** 1. mid\_a == mid\_b，那么mid\_a 和 mid\_b就是序列的中位数，因为这时候mid\_a两边的数字个数相同吗，所以一定是。 2. mid\_a < mia\_b，那么我们可以确定mid\_a左侧偏小的数，和mid\_b右侧偏大的数肯定不包含中位数，所以我们可以舍去序列A和B的各一半。 3. mid\_a > mid\_b，和2同理。 所以这样，我们每次舍弃一半的数，直至找到，这样做的时间复杂度是O(lgn)级别的，并且空间复杂度是O(1)，需要注意的是，舍弃的时候一定要保证A B舍弃的元素个数相同，否则就不对了。 ##### 代码 ##### int find_two_mid(int A[], int lena, int B[], int lenb) { int la = 0, ra = lena - 1; int lb = 0, rb = lenb - 1; while (la < ra) { int mida = la + ra >> 1; int midb = lb + rb >> 1; if (A[mida] == B[midb]) return A[mida]; else if (A[mida] > B[midb]){ ra = mida; lb = (rb - lb + 1) & 1 ? midb : midb + 1; // 这个判断保证舍弃时，两个序列舍弃的个数相同 } else { la = (ra - la + 1) & 1 ? mida : mida + 1; rb = midb; } } return min(A[la], B[lb]); } # 第十二题 # ##### 题目简介 ##### 找出序列中的主元素，主元素定义为序列中出现次数超多一半的元素。 ##### 思路分析 ##### 主元素有个特征，比一半的元素个数还多，假设把主元素看成是正电荷，其他元素看成是负电荷，中和后，整个序列是正电的，而且中和后只剩了主元素。 所以我们可以先模拟这种配对的思路，挑选出来一个为主元素的可以元素，然后再判断该元素是不是。 怎么配对里？先把第一个元素作为预选元素，当该元素不能配对了，就换，这样的话，最后留下的元素一定是最可能是主元素的元素。 ##### 代码 ##### int find_main_elemtype(int A[], int length) { if (length == 0) return -1; int value = A[0], cnt = 1; // 挑选出可能是主元素的元素 for (int i = 1; i < length; i++){ if (A[i] == value) cnt++; else { if (cnt == 0){ value = A[i]; cnt = 1; } else{ cnt--; } } } cnt = 0; // 验证元素是不是主元素 for (int i = 0; i < length; i++) { if (A[i] == value) cnt++; } return cnt >(length >> 1) ? value : -1; } # 第十三题 # ##### 题目简介 ##### 找出数组中从未出现的最小正整数。 ##### 题目分析 ##### 这是典型的空间换时间的一种题目，如果我们不开额外空间的话，我能想到的比较快就做法就是把数组排个序，然后扫一遍，这样最快是O(lgn)。如果我们使用额外O(n)的空间的话，可以把时间复杂度降到O(n)。 但是开空间的话有个小技巧，平常我们用把数当成数组下标去记录，这样的话，我们需要开O(max(A1, A2, … , An))空间，数组中最大的数个空间，但是这个题目很是巧妙了，比如数组的长度是n，我们只需要开O(n)，的空间，因为数组中从未出现的最小正整数只可能是1 ~ n + 1，这样的话，如果出现了大于n的数，我们根本不需要去记录，没什么意义，这个地方大家一定要仔细去体会。 ##### 代码 ##### int find_p13(int A[], int lena) { int* cnt = new int[lena + 1]; // 开一块辅助空间 memset(cnt, 0, sizeof(cnt) * (lena + 1)); for (int i = 0; i < lena; i++) { if (A[i] <= lena && A[i] > 0) cnt[A[i]] = 1; } for (int i = 1; i <= lena; i++){ if (!cnt[i]) return i; } return lena + 1; }
还没有评论，来说两句吧...