2.4 归纳总结与思维拓展
原书定位
印刷页P61起,对应PDF第73页。下文为目视整理的知识提要;完整内容见原书对照。
线性表算法题先讲思路、再给实现、最后分析时空复杂度。常用模式如下:
- 数组:双指针压缩筛除,首尾交换逆置,多次逆置循环移位,归并有序序列,投票法找主元素后再次验证。
- 链表:头插逆置、尾插保序、归并求交、快慢指针找中点与判环、固定间距指针找倒数第 项、长度对齐找公共后缀。
- 求两数和:排序后令两个指针从两端向内移动,比较和与目标值,总时间 ;要求每对只输出一次时还要处理重复值。
- 公共结点应比较结点地址;相同的数据值不代表两个链表共享存储。
关联知识
原书对照
展开原书对照截图
