2.4 归纳总结与思维拓展

教材导航 · 第2章

原书定位

印刷页P61起,对应PDF第73页。下文为目视整理的知识提要;完整内容见原书对照。

线性表算法题先讲思路、再给实现、最后分析时空复杂度。常用模式如下:

  • 数组:双指针压缩筛除,首尾交换逆置,多次逆置循环移位,归并有序序列,投票法找主元素后再次验证。
  • 链表:头插逆置、尾插保序、归并求交、快慢指针找中点与判环、固定间距指针找倒数第 kk 项、长度对齐找公共后缀。
  • 求两数和:排序后令两个指针从两端向内移动,比较和与目标值,总时间 O(nlog⁡n)O(n\log n);要求每对只输出一次时还要处理重复值。
  • 公共结点应比较结点地址;相同的数据值不代表两个链表共享存储。

关联知识

原书对照

展开原书对照截图

原书对照,原书P61,PDF第73页