2.2.3, 08
- 暴力方法，再开一个数组，然后就是循环！
- 一次循环不行，两次!
- 参数 m 和 n 为两个线性表的长度
- 时间复杂度O(m+n)，空间复杂度O(m+n)
void change(SqList &list, int m, int n) { // 前一个线性表[0, m-1], 后一个[m, m+n-1] SqList copied = list; int k = -1; for (int i = m; i < m+n; i++) { copied.data[++k] = list.data[i]; } for (int i = 0; i < m; i++) { copied.data[++k] = list.data[i]; } list = copied; } 复制代码
- 当然还有一种四两拨千斤的方法，可以先逆置整个数组，再分别逆置其中的两个线性表
- 比如说[1, 2, 3, 4]逆置成[4, 3, 2, 1]，然后其中一个线性表[4, 3]逆置成[3, 4]，另一个[2, 1]逆置成[1, 2]，最后结果就是[3, 4, 1, 2]
- 时间复杂度O(m+n)，空间复杂度O(1)
// 逆置，跟第二题类似, l=left, r=right void reverse(SqList &list, int l, int r) { if (l > r || r > list.length) return; int mid = (l + r) / 2; // 注意边界 for (int i = 0; i <= mid - l; i++) { swap(list.data[l+i], list.data[r-i]); } } void change2(SqList &list, int m, int n) { // 注意参数 reverse(list, 0, m+n-1); reverse(list, 0, n-1); reverse(list, n, m+n-1); } 复制代码
2.2.3, 09
- 递增有序，暴力循环
- 需要考虑很多边界条件，容易出错
- 时间复杂度O(n)，空间复杂度O(1)
void find_x2(SqList &list, int x) { // 1.二分找x int low = 0, high = list.length - 1, mid; while (low <= high) { mid = (low + high) / 2; if (list.data[mid] == x) break; else if (list.data[mid] < x) low = mid + 1; else high = mid - 1; } // 2.找到了 if (list.data[mid] == x && mid != list.length - 1) { swap(list.data[mid], list.data[mid + 1]); return; } // 3.没找到, 此时low>high list.length++; int i = list.length - 2; while (i > high) { list.data[i + 1] = list.data[i]; i--; } list.data[i + 1] = x; } 复制代码
- 优化，使用二分查找，不需要特别记录i的值
- 当查找失败时，high 会记录到最后一个小于x的元素
- 时间复杂度O(log2n)，空间复杂度O(1)
void find_x2(SqList &list, int x) { int low = 0, high = list.length - 1, mid; while (low <= high) { mid = (low + high) / 2; if (list.data[mid] == x) break; else if (list.data[mid] < x) low = mid + 1; else high = mid - 1; } // 找到了并且不是最后一个元素 if (list.data[mid] == x && mid != list.length - 1) { swap(list.data[mid], list.data[mid + 1]); return; } // 没找到 list.length++; int i = list.length - 2; while (i > high) { list.data[i + 1] = list.data[i]; i--; } list.data[i + 1] = x; }
