2.2.3, 10
- 这个真题跟第8题基本一样，我们可以直接copy过来改一下参数
- 首先就是暴力求解，新开一个数组，分别复制进去（把结构体改成数组是一样的）
- 这样的时间复杂度是O(n)，空间复杂度也是O(n)
- 为了节省空间，也可以创建一个大小为p的数组暂存前一个数组[0, p-1]，原数组整体左移后再依次放回，这样的空间复杂度会降到O(p)
void change(SqList &list, int p, int n) { // 1.左右两个数组分别是[0, p-1], [p, n-1] SqList copied = list; int k = -1; // 2.分别复制进去 for (int i = p; i < n; i++) { copied.data[++k] = list.data[i]; } for (int i = 0; i < p; i++) { copied.data[++k] = list.data[i]; } // 3.新换旧 list = copied; } 复制代码
- 四两拨千斤，整体逆置，再分别逆置
- 比如说[1, 2, 3, 4]逆置成[4, 3, 2, 1]，然后其中一个数组[4, 3]逆置成[3, 4]，另一个[2, 1]逆置成[1, 2]，最后结果就是[3, 4, 1, 2]
- 时间复杂度O(n)，空间复杂度O(1)
void reverse(SqList &list, int l, int r) { if (l > r || r > list.length) return; for (int i = 0; i < (r-l+1)/2 ; i++) { swap(list.data[l+i], list.data[r-i]); } } void change2(SqList &list, int p, int n) { // 注意参数 reverse(list, 0, n); reverse(list, 0, p); reverse(list, p, n); } 复制代码
2.2.3, 11
- 找到两个有序序列合并后的中位数，那暴力解就直接合并呗
- 可以把第7题直接抄过来，然后返回
(A.length + B.length)/2位置上的数即可 - 然后你会发现并不需要合并全部，也不需要一个辅助表来存储数据，只需要循环到这个位置就可以了
- 注意题目中要求，mid 应该等于
(A.length + B.length - 1) / 2 - 时间复杂度O(n)，空间复杂度O(1)
int merge(SqList A, SqList B) { int i = 0, j = 0, k = -1, mid = (A.length + B.length - 1) / 2; // 条件也不需要，因为我们找到中间值就会直接return while (1) { ++k; if (A.data[i] <= B.data[j]) { if (k == mid) return A.data[i]; i++; } else { if (k == mid) return B.data[j]; j++; } } } 复制代码
- 也可以直接循环到 mid 处，不需要每次都判断一次
==mid
int merge2(SqList A, SqList B) { int i = 0, j = 0, mid = (A.length + B.length - 1) / 2 ; while (i+j < mid) { if (A.data[i] <= B.data[j]) i++; else j++; } return A.data[i] < B.data[j] ? A.data[i] : B.data[j]; } 复制代码
- 考试不建议最优解，时间成本太高(大佬除外)，毕竟暴力解最多好像只有5分差距，没必要
- 我这里就不写了，可以看一下王道答案
