2.2.3, 6
- 有序列表 ➡️ 相同元素排列在一起
- 暴力，新开一个数组，将不同元素存入
- 需要两个指针分别操作两个数组
- 时间复杂度O(n)，空间复杂度O(n)
void del_same(SqList &list) { if (list.length == 0) return; // 1.新开一个数组 SqList copied = list; copied.data[0] = list.data[0]; // 2.把不同元素存入 int k = 0; for (int i = 1; i < list.length; i++) { if (list.data[k] != copied.data[i]) { copied.data[++k] = list.data[i]; } } // 3.新换旧 copied.length = k + 1; list = copied; } 复制代码
- 仔细想想，其实并不需要两个数组，双指针就可以
- 前一个存储，后一个判断
- 时间复杂度O(n)，空间复杂度O(1)
void del_same2(SqList &list) { if (list.length == 0) return; int k = 0; for (int i = 1; i < list.length; i++) { if (list.data[k] != list.data[i]) { list.data[++k] = list.data[i]; } } list.length = k + 1; } 复制代码
2.2.4, 7
- 这种题太典型了，合并有序顺序表以及合并有序链表，建议全文背诵hh
- 循环，取下两个之中的较小的放入结果表中
- 最后那个表还有剩余就把剩下的部分全部加入结果表
- 时间复杂度O(n)，空间复杂度O(n)
SqList merge(SqList A, SqList B) { SqList C; if (A.length + B.length > MaxSize) { cout << "ERROR!" << endl; return C; } int i = 0, j = 0, k = 0; // 1.两两比较，小的存入结果表 while (i < A.length && j < B.length) { if (A.data[i] <= B.data[j]) C.data[k++] = A.data[i++]; else C.data[k++] = B.data[j++]; } // 2.剩下的全部加入结果表，两个循环只会有一个运行 while (i < A.length) C.data[k++] = A.data[i++]; while (i < B.length) C.data[k++] = B.data[j++]; // 3.返回结果表 C.length = k; return C; } 复制代码
- 补充一下归并排序
void merge_sort(int l, int r) { if (l >= r) return; int mid = (l+r) >> 1; merge_sort(l, mid); merge_sort(mid+1, r); int k = 0, i = l, j = mid+1; while (i <= mid && j <= r) { if (q[i] <= q[j]) tmp[k++] = q[i++]; else tmp[k++] = q[j++]; } while (i <= mid) tmp[k++] = q[i++]; while (j <= r) tmp[k++] = q[j++]; for (i = l, j = 0; i <= r; i++, j++) q[i++] = tmp[j++]; }
