罗罗编程学习记录
本页内容 展开查看

02.5 二分与排序

所属:全栈开发面试题库 / 02 数据结构与算法

覆盖范围

  • 二分区间定义、lower/upper_bound、边界防死循环、mid 防溢出、不变量
  • 旋转数组分段有序查找、找最小值、重复元素退化、局部峰谷
  • 二分答案:可行单调、check 判定、最大/最小可行值、吃香蕉、分割数组、运包裹
  • 二维有序矩阵搜索、第 K 小、二维峰值、单调函数求根、BST 查找
  • 基础排序与稳定性:冒泡/选择/插入、复杂度对比、计数/桶/基数概念
  • 快排与三路划分:Lomuto/Hoare、pivot 策略、快速选择、荷兰国旗
  • 归并排序与逆序对:稳定归并、链表归并、逆序对批量计数、右侧更小元素
  • 堆排序与工程排序:堆排、Top-K 堆、双堆中位数、外部排序多路归并、选型

子主题

编号 主题 覆盖范围
02.5.1 二分查找 4 个子主题 80 题:模板与边界、旋转数组与部分有序、二分答案、二维矩阵与非数组二分
02.5.2 排序算法与设计 4 个子主题 80 题:基础排序与稳定性、快排与三路划分、归并与逆序对、堆排序与工程排序

面试题索引

编号 题目 难度 频率 所在页面
02.5.1.1-002 基本二分查找(LC 704) 简单 ★★★★★ 二分模板与边界
02.5.1.1-004 lower_bound 第一个 ≥ target 中等 ★★★★★ 二分模板与边界
02.5.1.1-010 搜索插入位置(LC 35) 简单 ★★★★☆ 二分模板与边界
02.5.1.2-002 搜索旋转排序数组(LC 33) 中等 ★★★★★ 旋转数组与部分有序
02.5.1.2-003 旋转数组含重复(LC 81) 中等 ★★★☆☆ 旋转数组与部分有序
02.5.1.2-004 找旋转数组最小值(LC 153) 中等 ★★★★☆ 旋转数组与部分有序
02.5.1.3-005 爱吃香蕉的珂珂(LC 875) 中等 ★★★★☆ 二分答案
02.5.1.3-006 分割数组最大值(LC 410) 困难 ★★★★☆ 二分答案
02.5.1.3-007 运送包裹(LC 1011) 中等 ★★★★☆ 二分答案
02.5.1.4-002 搜索二维矩阵 I(LC 74) 中等 ★★★★☆ 二维矩阵与非数组二分
02.5.1.4-003 搜索二维矩阵 II(LC 240) 中等 ★★★★☆ 二维矩阵与非数组二分
02.5.1.4-007 有序矩阵第 K 小(LC 378) 中等 ★★★☆☆ 二维矩阵与非数组二分
02.5.2.1-007 常见排序稳定性对比 基础 ★★★★★ 基础排序与稳定性
02.5.2.1-008 常见排序复杂度对比 基础 ★★★★★ 基础排序与稳定性
02.5.2.2-001 快速排序基本思想 中等 ★★★★★ 快排与三路划分
02.5.2.2-007 三路划分解决重复元素 中等 ★★★★☆ 快排与三路划分
02.5.2.2-010 快速选择第 K 大(LC 215) 中等 ★★★★★ 快排与三路划分
02.5.2.2-014 荷兰国旗问题(LC 75) 中等 ★★★★☆ 快排与三路划分
02.5.2.3-002 归并排序实现 中等 ★★★★★ 归并排序与逆序对
02.5.2.3-008 归并求逆序对 困难 ★★★★☆ 归并排序与逆序对
02.5.2.4-006 第 K 大元素堆法(LC 215) 中等 ★★★★★ 堆排序与工程排序
02.5.2.4-008 外部排序概念与流程 高级 ★★★☆☆ 堆排序与工程排序
02.5.2.4-018 排序选型总结 基础 ★★★★☆ 堆排序与工程排序

当前状态

  • 02.5.1 已完成 4 个子主题、80 题;02.5.2 已完成 4 个子主题、80 题,合计 160 题,全部为可学习型详解。
  • 页面结构:知识域首页 + 子主题页 + 分册 TOC 三层登记。
  • 代码以 Java 为主;复杂度标注平均/最坏/均摊口径,不确定版本行为标注待确认。