第4周内容

周子力2025年9月26日大约 9 分钟教学文档算法设计与分析

递归与分治

1.上周内容

（1）分治策略与分治算法设计模式及性质

合并排序与逆序对问题

快速排序与快速选择算法（找第k大，或第k小的元素）

基础功

（1）看到是一组数据，马上考虑到用一种数据结构来表示，比如，是用数组？还是用链表？是用栈？还是用队列？是用树？还是图？

（2）要对这些数据结构的操作熟悉，比如数组的分段操作，栈的入栈和出栈操作，队列的入队和出队操作，树的遍历操作等。

如：对于数组，判断是否为空，可以用 left 和 right 比较，来判断是否为空。如果是链表，判断是否为空，可以用 head == null 来判断。如果是树，判断是否为空，可以用 root == null 来判断。如果是图，判断是否为空，可以用 graph.isEmpty() 来判断。

对于数组，可以通过left 和 right 对数组进行分段操作，比如求中间位置的操作。如果是链表，可以通过 head 和 tail 对链表进行遍历和修改等操作。

对于树，可以通过 root 对整棵树进行遍历和修改等操作。如果是图，可以通过 graph.getEdges() 来获取所有的边，并通过这些边来构建整个图的拓扑结构。

对于栈，可以通过 push 和 pop 对数据进行入栈和出栈操作。如果是队列，可以通过 enqueue 和 dequeue 对数据进行入队和出队操作。如果是树，可以通过 insert 和 delete 对节点进行插入和删除等操作。如果是图，可以通过 addEdge 和 removeEdge

（3）在写代码的时候，要考虑到边界条件。比如数组为空或者只有一个元素的时候怎么处理？链表的头节点或者尾节点怎么处理？树的高度为0的时候怎么处理？

目前我们遇到的基本都是数组相关的操作问题，比如在如果用数组作为函数的参数，是传整个数组？还是传数组的同量，把左右边界作为参数？

这里面的细节问题，只有通过不断的练习，才能熟练掌握。

2.真题实战

(1) 连续数列

一、代码实现中的注意事项

递归基（Base Case）的处理：这是分治法最容易出错的地方。当子数组的长度为1时（即 left == right），不能再继续分割，此时最大子数组和就是该元素本身。必须正确处理这个边界条件，否则递归会无限进行下去或者产生错误结果。
“跨越中点”情况的精确计算：这是分治法的核心，也是最容易写错的部分。
- 方向性：计算左半部分的最大和时，必须从中间点 mid 开始向左遍历，并且必须包含 mid。同理，计算右半部分的最大和时，必须从 mid + 1 开始向右遍历，并且必须包含 mid + 1。不能反向计算，否则就无法保证子数组是连续且跨越中点的。
- 初始化：左右两部分的初始和通常设为负无穷（或一个极小的数），但在累加过程中，第一个元素（nums[mid] 和 nums[mid+1]）必须被包含进来。
- 累加方式：应该一边遍历一边累加，并实时更新当前找到的最大和，而不是先计算所有可能的和再取最大值，那样会增加不必要的复杂度。
返回值的正确比较：在每一层递归中，必须正确地比较三种情况（左半部分最大值、右半部分最大值、跨越中点的最大值），并返回三者中的最大值。
数组索引的边界：在分割数组和遍历时，要时刻注意数组的左右边界 left 和 right，避免数组越界错误。

二、对题目的思考

分治法的优劣：
- 优点：思路清晰，完美体现了“分而治之”的算法思想，将一个复杂问题分解为规模更小的相同子问题。对于理解递归和分治策略非常有帮助。
- 缺点：时间复杂度为 O(n log n)。虽然优于暴力解法的 O(n²)，但存在更优的解法。例如，动态规划（Kadane算法） 可以在线性时间 O(n) 内解决此问题，空间复杂度也更低（O(1)）。因此，在实际工程应用中，动态规划通常是首选。
问题的本质：这个问题考察的是如何在包含正负数的序列中，高效地找到一个局部最优的连续片段。负数是“破坏者”，会拉低总和；正数是“贡献者”。算法的核心在于如何聪明地“绕过”或“吸收”负数的影响。动态规划的思路是“如果之前的累计和是负的，那么从当前元素重新开始会更好”，这非常直观且高效。
三种情况的完备性：分治法将问题分为“左”、“右”、“跨中”三种情况，这三种情况是互斥且完备的。任何一个连续子数组，其位置必然属于这三种情况之一，不会有遗漏。这是分治法能够正确求解此问题的理论基础。
扩展性思考：如果题目稍作变化，比如要求返回最大和子数组的起始和结束索引，分治法和动态规划法都可以进行修改来实现，但动态规划法的修改通常更为直接。

(2)两个有序数组中位数

代码注意事项

1. 数组长度处理

if len(nums1) > len(nums2):
    nums1, nums2 = nums2, nums1

为什么这样做？ 确保在较短的数组上进行二分查找，时间复杂度为 O(log(min(m,n)))，这是优化的关键
不这样做的后果？ 如果在较长数组上二分，虽然仍满足 O(log(m+n))，但实际性能较差

2. 分割点计算的精确性

half = (total + 1) // 2
j = half - i

为什么是 (total + 1) // 2？
- 确保左半部分元素数 ≥ 右半部分元素数
- 奇数长度时，左半部分多一个元素（中位数在左半部分）
- 偶数长度时，左右部分元素数相等

3. 边界条件的处理

nums1_left_max = float('-inf') if i == 0 else nums1[i - 1]
nums1_right_min = float('inf') if i == m else nums1[i]

边界情况包括：
- 一个数组完全在左半部分（i = m 或 j = n）
- 一个数组完全在右半部分（i = 0 或 j = 0）
- 空数组的情况
使用无穷大/小值的意义： 避免数组越界，同时在比较时不会影响逻辑判断

4. 二分查找的移动方向

if nums1_left_max > nums2_right_min:
    right = i - 1  # nums1左半部分太大，需要左移
else:
    left = i + 1   # nums2左半部分太大，需要右移

移动逻辑的理解： 当分割不正确时，需要调整分割点使左右两部分平衡

5. 中位数计算的奇偶处理

if total % 2 == 1:
    return max(nums1_left_max, nums2_left_max)
else:
    return (max(nums1_left_max, nums2_left_max) + min(nums1_right_min, nums2_right_min)) / 2.0