排序、搜索与算法设计¶
排序和搜索是最基础的算法操作。本篇涵盖排序算法、二分查找模式、分治法、贪心算法、动态规划以及回溯。
- 每种数据结构都服务于算法，每个算法也都依赖数据结构。本篇讲解设计范式：解决问题的顶层策略。一旦你识别出应该使用哪种范式，实现就水到渠成了。
排序算法¶
- 排序是计算机科学中研究最多的问题。理解这些算法有助于建立递归、分治法和复杂度分析的直觉。
| 算法 | 最优 | 平均 | 最差 | 空间 | 稳定？ |
|---|---|---|---|---|---|
| 冒泡排序 | \(O(n)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | 是 |
| 插入排序 | \(O(n)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | 是 |
| 归并排序 | \(O(n \log n)\) | \(O(n \log n)\) | \(O(n \log n)\) | \(O(n)\) | 是 |
| 快速排序 | \(O(n \log n)\) | \(O(n \log n)\) | \(O(n^2)\) | \(O(\log n)\) | 否 |
| 堆排序 | \(O(n \log n)\) | \(O(n \log n)\) | \(O(n \log n)\) | \(O(1)\) | 否 |
| 计数排序 | \(O(n + k)\) | \(O(n + k)\) | \(O(n + k)\) | \(O(k)\) | 是 |
| 基数排序 | \(O(d(n + k))\) | \(O(d(n + k))\) | \(O(d(n + k))\) | \(O(n + k)\) | 是 |
-
稳定 意味着相等元素保持它们原来的相对顺序。这对多关键字排序很重要。
-
基于比较的排序下界为 \(\Omega(n \log n)\)。证明使用决策树（第13章）：任何比较排序必须区分所有 \(n!\) 种排列，至少需要 \(\log_2(n!) = \Omega(n \log n)\) 次比较。计数排序和基数排序通过不比较元素来突破这个下界。
归并排序¶
- 将数组对半分成两半，递归地对每半排序，然后合并已排序的两半。始终为 \(O(n \log n)\)，额外空间 \(O(n)\)。
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= 保持稳定性
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
- 陷阱：在合并中使用
<而不是<=会破坏稳定性（来自右半部分的相等元素会排在左半部分之前）。
快速排序¶
- 选择一个枢轴，将元素分成“小于枢轴”和“大于枢轴”两部分，递归地对每部分排序。平均 \(O(n \log n)\)，最坏 \(O(n^2)\)（当枢轴总是最小或最大元素时）。
def quicksort(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if lo >= hi:
return
pivot_idx = partition(arr, lo, hi)
quicksort(arr, lo, pivot_idx - 1)
quicksort(arr, pivot_idx + 1, hi)
def partition(arr, lo, hi):
pivot = arr[hi] # Lomuto 划分：枢轴取最后一个元素
i = lo
for j in range(lo, hi):
if arr[j] < pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[hi] = arr[hi], arr[i]
return i
-
枢轴选择策略：最后一个元素（简单，但对已排序数组糟糕）、随机（期望 \(O(n \log n)\)）、三数取中（实用选择）。面试中总是倾向于随机枢轴，以避免讨论最坏情况。
-
陷阱：快速排序的最坏情况 \(O(n^2)\) 发生在已排序数组且选择第一个或最后一个作为枢轴时。实践中，随机枢轴或三数取中能消除这个问题。
计数排序¶
- 当值是已知范围 \([0, k)\) 内的整数时，统计出现次数并重建：\(O(n + k)\) 时间。不是基于比较的，因此可以超越 \(O(n \log n)\)。
def counting_sort(arr, k):
count = [0] * k
for x in arr:
count[x] += 1
result = []
for val in range(k):
result.extend([val] * count[val])
return result
- 何时使用：范围 \(k\) 与 \(n\) 相差不大。如果 \(k = O(n)\)，则复杂度为 \(O(n)\)。如果 \(k \gg n\)（例如对 10 个范围在 \([0, 10^9]\) 的数排序），计数排序会浪费内存。
模式：二分查找¶
-
二分查找通过在有序数组中反复减半搜索空间，以 \(O(\log n)\) 时间找到目标。但二分查找远不止“在有序数组中找一个数”。它的通用模式是：在单调条件上进行搜索。
-
模板（能避免差一错误的版本）：
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2 # 避免（其他语言中）的溢出
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1 # 未找到
- 下界（第一个 \(\geq\) 目标值的元素）：
def lower_bound(arr, target):
lo, hi = 0, len(arr)
while lo < hi:
mid = (lo + hi) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
- 陷阱：
lo <= hi与lo < hi的区别，以及hi = mid与hi = mid - 1的区别，决定了你是找到精确匹配还是边界。用一个两个元素的数组画出来验证。
简单：二分查找¶
- 标准问题。使用上面的模板。
中等：搜索旋转排序数组¶
-
问题：一个有序数组在某个枢轴处旋转。找到目标值。
-
模式：每一步中，总有一半是有序的。确定哪一半是有序的，然后检查目标是否落在这个有序半段中。
def search_rotated(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
# 左半段有序
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
# 右半段有序
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
- 陷阱：
<=在nums[lo] <= nums[mid]中（而不是<）至关重要。当lo == mid（还剩两个元素）时，我们必须正确识别有序的半段。
困难：两个有序数组的中位数¶
-
问题：在 \(O(\log(m + n))\) 时间内找到两个有序数组的中位数。
-
模式：在较短数组的分割点上进行二分查找。分割点将两个数组分成左右两部分，使得左半部分的所有元素都小于右半部分的所有元素。
def find_median(nums1, nums2):
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1 # 确保 nums1 更短
m, n = len(nums1), len(nums2)
lo, hi = 0, m
half = (m + n + 1) // 2
while lo <= hi:
i = (lo + hi) // 2 # nums1 中的分割点
j = half - i # nums2 中的分割点
left1 = nums1[i - 1] if i > 0 else float('-inf')
right1 = nums1[i] if i < m else float('inf')
left2 = nums2[j - 1] if j > 0 else float('-inf')
right2 = nums2[j] if j < n else float('inf')
if left1 <= right2 and left2 <= right1:
# 找到正确分割
if (m + n) % 2 == 1:
return max(left1, left2)
return (max(left1, left2) + min(right1, right2)) / 2
elif left1 > right2:
hi = i - 1
else:
lo = i + 1
- 这是最难的一类二分查找问题。关键洞察是：你搜索的不是一个值，而是一个满足条件的分割点。
元模式：在答案上二分¶
-
许多看起来不像二分查找的问题，可以通过在答案上进行二分查找来解决。如果答案是一个数，并且你能写出一个函数
is_feasible(x)，该函数是单调的（对于所有 \(x \geq\) 最优值为 True，或对于所有 \(x \geq\) 最优值为 False），那么就可以在 \(x\) 上进行二分查找。 -
例子：“能在 \(d\) 天内运送完所有包裹的船的最小运载能力是多少？” 在运载能力上二分查找。对于每个候选运载能力，贪心地检查是否能在 \(d\) 天内运送完所有包裹。
def ship_within_days(weights, days):
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = (lo + hi) // 2
# 能否用运载能力 mid 在 <= days 天内运完？
current_load, num_days = 0, 1
for w in weights:
if current_load + w > mid:
num_days += 1
current_load = 0
current_load += w
if num_days <= days:
hi = mid
else:
lo = mid + 1
return lo
模式：贪心算法¶
- 贪心算法在每一步做出局部最优选择，希望这能导致全局最优解。贪心算法适用于问题具有贪心选择性质（局部最优导致全局最优）和最优子结构（最优解包含子问题的最优解）。
中等：跳跃游戏¶
- 问题：给定一个数组
nums[i]表示在位置 \(i\) 的最大跳跃长度，判断是否能到达最后一个下标。
def can_jump(nums):
max_reach = 0
for i, jump in enumerate(nums):
if i > max_reach:
return False # 无法到达此位置
max_reach = max(max_reach, i + jump)
return True
- 为什么贪心有效：我们只需要知道最远可到达的位置。如果当前位置已经超出了最远到达距离，就卡住了。否则，更新最远到达距离。
中等：合并区间¶
- 问题：合并重叠的区间。
def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
-
模式：按开始时间排序，然后贪心地合并。如果当前区间与最后一个合并区间重叠，就扩展它。否则，开始一个新的合并区间。
-
陷阱：使用
merged[-1][1] = end而不是merged[-1][1] = max(merged[-1][1], end)。一个区间可能完全包含在另一个区间内（例如 [1,10] 和 [2,5]）。
模式：动态规划¶
-
动态规划（DP） 通过将问题分解为重叠的子问题，每个子问题只求解一次并存储结果，从而解决问题。它适用于具有最优子结构和重叠子问题的问题。
-
两种方法：
- 自顶向下（记忆化）：写出自然的递归解法，然后在字典中缓存结果。
- 自底向上（制表）：从最小的子问题开始向上构造表格。
-
如何识别DP：问题要求最优化（最小/最大）、计数或存在性，且当前决策依赖于之前的决策。如果你画出递归树并看到重复的子问题，那就是DP。
简单：爬楼梯¶
-
问题：\(n\) 级台阶，每次可以爬 1 或 2 级，有多少种不同的方法？
-
这就是斐波那契：\(f(n) = f(n-1) + f(n-2)\)。
def climb_stairs(n):
if n <= 2:
return n
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b
return b
- \(O(n)\) 时间，\(O(1)\) 空间。不需要完整的记忆化表格，因为每个状态只依赖于前两个状态。
中等：零钱兑换¶
-
问题：给定硬币面额和目标金额，找出所需的最少硬币数。
-
状态：
dp[amount]= 凑成amount所需的最少硬币数。 - 转移：
dp[amount] = min(dp[amount - coin] + 1)对每种硬币。 - 基本情况：
dp[0] = 0。
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for coin in coins:
if coin <= a and dp[a - coin] + 1 < dp[a]:
dp[a] = dp[a - coin] + 1
return dp[amount] if dp[amount] != float('inf') else -1
- 陷阱：初始化为
float('inf')（而不是 0 或 -1）。只有不可达状态为无穷大时，最小值比较才能正确工作。
中等：最长公共子序列¶
-
问题：给定两个字符串，求它们的最长公共子序列的长度。
-
状态：
dp[i][j]=text1[:i]和text2[:j]的 LCS 长度。 - 转移：如果
text1[i-1] == text2[j-1]，则dp[i][j] = dp[i-1][j-1] + 1。否则dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
def longest_common_subsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
困难：0/1 背包问题¶
-
问题：给定物品的重量和价值，以及背包容量 \(W\)，在不超过容量的前提下最大化总价值。
-
状态：
dp[i][w]= 使用前 \(i\) 个物品、容量为 \(w\) 时的最大价值。 - 转移：
dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])（跳过或取物品 \(i\)）。
def knapsack(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
dp[i][w] = dp[i - 1][w] # 跳过物品 i
if weights[i - 1] <= w:
dp[i][w] = max(dp[i][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1])
return dp[n][capacity]
- 空间优化：因为每一行只依赖上一行，可以使用一维数组，并从右向左遍历 \(w\)：
def knapsack_optimised(weights, values, capacity):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
for w in range(capacity, weights[i] - 1, -1): # 从右向左！
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
- 陷阱：在一维版本中从左向右遍历会允许重复使用同一个物品（完全背包）。从右向左遍历保证每个物品最多使用一次。
模式：回溯¶
-
回溯 是带剪枝的穷举搜索。逐步构建解，一旦发现部分解不可能导向有效的完整解，就放弃（回溯）。
-
模板：
def backtrack(candidates, path, result):
if is_solution(path):
result.append(path[:]) # 复制！
return
for candidate in get_candidates(path):
if is_valid(candidate, path):
path.append(candidate) # 选择
backtrack(candidates, path, result) # 探索
path.pop() # 撤销选择（回溯）
中等：子集¶
def subsets(nums):
result = []
def backtrack(start, path):
result.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
中等：组合总和¶
- 问题：找出所有不重复的组合，使其和等于目标值（元素可以重复使用）。
def combination_sum(candidates, target):
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
break # 剪枝：已排序，后续候选值都太大
path.append(candidates[i])
backtrack(i, path, remaining - candidates[i]) # i, 不是 i+1：允许重复使用
path.pop()
candidates.sort() # 为了剪枝而排序
backtrack(0, [], target)
return result
- 陷阱：
backtrack(i， ...)允许重复使用同一个元素。backtrack(i + 1, ...)则会移动到下一个元素（不允许重复使用）。弄错这点是最常见的回溯错误。
困难：N 皇后¶
- 问题：在 \(n \times n\) 的棋盘上放置 \(n\) 个皇后，使得它们互不攻击。
def solve_n_queens(n):
result = []
cols = set()
pos_diag = set() # (行 + 列) 在 / 对角线上是常数
neg_diag = set() # (行 - 列) 在 \ 对角线上是常数
board = [['.' ] * n for _ in range(n)]
def backtrack(row):
if row == n:
result.append([''.join(r) for r in board])
return
for col in range(n):
if col in cols or (row + col) in pos_diag or (row - col) in neg_diag:
continue
cols.add(col)
pos_diag.add(row + col)
neg_diag.add(row - col)
board[row][col] = 'Q'
backtrack(row + 1)
cols.remove(col)
pos_diag.remove(row + col)
neg_diag.remove(row - col)
board[row][col] = '.'
backtrack(0)
return result
- 关键洞察：对角线的编码。对于
/对角线，row + col是常数。对于\对角线，row - col是常数。使用集合来跟踪列和对角线使有效性检查变为 \(O(1)\)。
常见陷阱总结¶
| 陷阱 | 示例 | 解决方法 |
|---|---|---|
二分查找中 lo <= hi 与 lo < hi |
边界差一 | 根据 hi 是包含还是排除来选择 |
| 一维背包从左向右遍历 | 物品被多次使用 | 0/1 背包从右向左遍历 |
| 回溯中没有复制路径 | result.append(path) — 所有条目指向同一个列表 |
result.append(path[:]) 或 path.copy() |
backtrack(i) 与 backtrack(i+1) |
元素是否可重复使用 | 与问题陈述一致 |
排序后回溯时缺少 break |
探索过大的候选值 | 排序 + 当候选值超过剩余值时 break |
| DP 初始化错误 | dp[0] 错 → 后续值全错 |
仔细定义基本情况 |
| 不经证明就使用贪心 | 贪心并非总是有效 | 验证贪心选择性质 |
| 多关键字排序使用不稳定排序 | 相等元素的相对顺序被破坏 | 使用稳定排序（归并排序、Python 的 sorted） |
课后练习（NeetCode）¶
二分查找¶
- 二分查找 — 标准模板
- 搜索二维矩阵 — 在展平的矩阵上二分
- Koko 吃香蕉 — 在答案上二分
- 搜索旋转排序数组 — 识别有序半段
- 寻找旋转排序数组中的最小值 — 二分找拐点
- 两个有序数组的中位数 — 基于分割点的二分
贪心¶
动态规划¶
- 爬楼梯 — 斐波那契 DP
- 打家劫舍 — 取或不取的 DP
- 打家劫舍 II — 环形：运行两次
- 零钱兑换 — 完全背包
- 最长公共子序列 — 两个字符串的二维 DP
- 单词拆分 — DP + 集合查找
- 最长递增子序列 — \(O(n^2)\) DP 或 \(O(n \log n)\) 带二分查找
- 编辑距离 — 经典二维 DP
- 分割等和子集 — 0/1 背包变种