排序

副标题 / 摘要 内存无法容纳 10GB 数据时，外部排序是标准方案。本文介绍分块排序与多路归并。 目标读者 需要处理大文件的工程师 学习外部排序算法的读者 关注磁盘 I/O 优化的人 背景 / 动机 当数据量超过内存容量，传统内存排序会失败。 外部排序通过“分块 + 多路归并”解决问题。 核心概念 分块排序：把大文件拆成可放入内存的小块 多路归并：合并多个有序块 磁盘 I/O：顺序读写优于随机读写 实践指南 / 步骤 按内存容量分块读取 每块内存排序并写回磁盘 多路归并所有有序块 尽量顺序读写减少随机 I/O 可运行示例 # 简化示例：分块排序 + 归并 import heapq def merge_sorted(chunks): heap = [] for i, chunk in enumerate(chunks): if chunk: heapq.heappush(heap, (chunk[0], i, 0)) result = [] while heap: val, i, j = heapq.heappop(heap) result.append(val) if j + 1 < len(chunks[i]): heapq.heappush(heap, (chunks[i][j + 1], i, j + 1)) return result if __name__ == "__main__": chunks = [sorted([3, 1, 2]), sorted([9, 7, 8])] print(merge_sorted(chunks)) 解释与原理 外部排序的核心是把“大问题拆成小问题”，每块可在内存中排序。 最后通过多路归并生成整体有序序列。 ...

副标题 / 摘要 10TB 数据无法在单机完成排序。本文介绍分布式排序的核心流程与工程要点。 目标读者 处理大规模数据的工程师 学习分布式系统的开发者 关注数据处理流程的人 背景 / 动机 数据规模超过单机能力时，必须通过分布式拆分与并行归并完成排序。 这涉及数据切分、网络传输与容错。 核心概念 分片（Shard）：数据切分到多个节点 Shuffle：按 key 重新分配数据 分布式归并：跨节点合并有序块 实践指南 / 步骤 按范围或哈希切分数据 各节点本地排序 Shuffle 让相同范围的数据聚集 全局归并并输出结果 可运行示例 # 简化的“分片排序”示意 def shard_sort(chunks): return [sorted(c) for c in chunks] def merge_two(a, b): i = j = 0 res = [] while i < len(a) and j < len(b): if a[i] < b[j]: res.append(a[i]); i += 1 else: res.append(b[j]); j += 1 res.extend(a[i:]) res.extend(b[j:]) return res if __name__ == "__main__": shards = shard_sort([[3, 1], [4, 2]]) print(merge_two(shards[0], shards[1])) 解释与原理 分布式排序的关键在于“局部排序 + 全局归并”。 Shuffle 会成为主要瓶颈，需要优化网络与分区策略。 ...

副标题 / 摘要 合并区间是最典型的“排序 + 线性扫描”问题：先按起点排序，再顺序合并重叠区间。本文按 ACERS 结构拆解题意、核心概念、工程迁移与多语言实现，帮助你形成可复用的区间处理模型。 预计阅读时长：12~15 分钟 标签：Hot100、区间、排序、扫描线、合并区间 SEO 关键词：Merge Intervals, 合并区间, 区间合并, 排序, 扫描线 元描述：合并区间的排序扫描解法与工程应用解析，含复杂度对比与多语言实现。 目标读者 想掌握“区间合并”基础模型的初学者 需要把算法思路迁移到工程场景的中级开发者 正在准备算法面试、希望快速建立区间类题型的求职者 背景 / 动机 区间问题在日程排班、监控窗口、日志聚合、资源分配中非常常见。 如果没有一个统一的合并策略，很容易产生重复统计、冲突判断错误或资源浪费。 因此，“把重叠区间合成最少的不重叠集合”是工程与算法都高频出现的基础能力。 A — Algorithm（题目与算法） 题目还原 给定一个区间数组 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间。 请合并所有重叠的区间，并返回一个不重叠的区间数组，且能完整覆盖输入中的所有区间。 输入输出 名称 类型 描述 intervals int[][] 区间数组，元素为 [start, end] 返回 int[][] 合并后的不重叠区间数组 基础示例（官方） 输入 输出 [[1,3],[2,6],[8,10],[15,18]] [[1,6],[8,10],[15,18]] [[1,4],[4,5]] [[1,5]] 合并示意（示例 1） 排序后: [1,3] [2,6] [8,10] [15,18] 合并: [1,3] + [2,6] -> [1,6] 结果: [1,6] [8,10] [15,18] 思路概览 按区间起点升序排序（起点相同则按终点升序）。 线性扫描，维护当前合并区间 [cur_start, cur_end]。 如果下一个区间 next_start <= cur_end，则合并为 cur_end = max(cur_end, next_end)。 否则将当前区间放入结果，并以新起点开始下一段合并。 C — Concepts（核心思想） 核心概念 概念 含义 作用 重叠 next_start <= cur_end 判断是否需要合并 合并 cur_end = max(cur_end, next_end) 扩展当前区间 排序 按起点排序 让重叠区间相邻 方法类型 排序 + 线性扫描 + 贪心合并。 ...

副标题 / 摘要 一道典型的“乘积 ≥ 阈值”计数题，看起来像是 O(n²) 的双重循环，实际上用「排序 + 二分查找」就能把复杂度压到 O((n+m)log m)。本文从题意抽象、核心公式到多语言实现，带你把这类阈值匹配问题彻底吃透。 预计阅读时长：10~15 分钟 适用场景标签：二分查找、排序计数、阈值匹配 SEO 关键词：spells and potions, successful pairs, 二分查找, lower_bound, 乘积约束 目标读者与背景 目标读者 已熟悉基本二分查找，想提升「在有序数组上做计数」能力的同学 后端 / 算法工程师，经常处理阈值判断与配对统计的问题 准备技术面试，希望积累“排序 + 二分”模板的开发者 为什么这题值得单独写一篇？ 它把一个表面 O(n²) 的「所有配对」问题，转化成了对有序数组的二分计数； 公式非常典型：把 a * b ≥ success 转成 b ≥ ceil(success / a)； 这种思路在推荐系统、风控额度、资源匹配等业务里屡见不鲜。 A — Algorithm（题目与算法） 题目重述 给定两个整数数组 spells 和 potions，以及一个正整数 success。 对于每个咒语 spells[i]，我们定义它与药水 potions[j] 的组合是“成功”的，当且仅当： spells[i] * potions[j] >= success 请返回一个数组 ans，其中 ans[i] 表示第 i 个咒语可以与多少个药水形成成功组合。 ...