★ FEATURED ARTICLE 示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本篇技术指南围绕《程序员面试金典第 6 版》中的困难题面试题 17.26 稀疏相似度Sparse Similarity展开完整继承并深入剖析该题在 doocs/leetcode 仓库 lcci/17.26.Sparse Similarity 中的官方题解以「单词 → 文档编号」倒排索引为骨架、以哈希表共现计数为核心的稀疏相似度算法。读完本文你将掌握相似度Jaccard 相似度的集合计算模型、倒排索引在只计算交集非空文档对场景下的剪枝威力以及五种主流语言下键编码、浮点精度修正等工程细节能够独立推导并实现这一经典面试算法。题目速览相似度定义与输出规范相似度的集合定义两个具有不同单词的文档的相似度定义为交集intersection元素个数除以并集union元素个数。例如{1, 5, 3}与{1, 7, 2, 3}交集元素{1, 3}共 2 个并集元素{1, 2, 3, 5, 7}共 5 个相似度 2 / 5 0.4。这一定义即信息检索领域通用的Jaccard 相似度。题目强调文档内元素互不相同即每个文档是一个集合这是后续并集 两篇长度之和 − 交集这一公式成立的前提。输入与输出格式输入是一个二维数组docs其中docs[i]表示 id 为i的文档每个文档由互不相同的整数组成。需要返回一个字符串数组每个元素代表一对相似度大于 0 的文档格式为{id1},{id2}: {similarity}其中id1是两文档中较小的 idsimilarity为相似度精确到小数点后 4 位数组可以任意顺序返回。官方示例输入[ [14, 15, 100, 9, 3], [32, 1, 9, 3, 5], [15, 29, 2, 6, 8, 7], [7, 10] ]输出[ 0,1: 0.2500, 0,2: 0.1000, 2,3: 0.1429 ]可以手工推演验证文档0与1交集为{9, 3}2 个并集为5 5 − 2 8相似度0.25文档2与3交集为{7}1 个并集为6 2 − 1 7相似度1/7 ≈ 0.142857保留四位小数即0.1429。其余文档对没有公共元素相似度为 0不进入结果。数据规模约束约束项上限文档个数docs.length≤ 500单篇文档长度docs[i].length≤ 500相似度大于 0 的文档对数≤ 1000相似度大于 0 的文档对数不超过 1000这一条正是题目名字中稀疏Sparse的数学刻画任意选两篇文档交集几乎总是空的真正需要输出的组合极少。为什么朴素两两建集合行不通最直接的思路是枚举每一对文档(i, j)各自建成集合后求交集与并集。但结合规模约束分析这种做法存在明显浪费文档个数与单篇长度都可达 500全量枚举C(500, 2) ≈ 12.5 万对每对都要建集合、求交并开销巨大由于相似度稀疏绝大多数文档对的交集为空但朴素方法仍然要为这些空交集构造并扫描集合题目明确保证真正需要计算的文档对不超过 1000时间应当只花在至少共现过一个单词的文档对上。关键洞察是两个文档相似度大于 0等价于它们至少共享一个单词。只要某个单词同时出现在一组文档中这组文档两两的交集就至少包含它。因此可以沿着每个单词把共现次数累加直接得到任意文档对的交集大小——完全不必为每个候选对重新扫描集合。核心思路倒排索引 共现计数整道题的三步解法如下第一步建立倒排索引d单词 → 文档编号列表。遍历所有文档把每个单词x出现的文档编号i追加到d[x]。由于文档按编号从小到大扫描且每个文档内整数互不相同d[x]中的编号严格递增——这一有序性在后面输出格式中会被直接利用。第二步沿倒排列表累加交集大小。对d中的每个文档编号列表枚举其中两两编号对(ids[i], ids[j])i j并在哈希表cnt中累加计数。键是文档编号对值是这两个文档的交集大小。两个文档共现过一个单词就在该键上贡献 1因此最终计数恰好等于交集元素个数。第三步由长度关系计算相似度。文档长度已知并集等于两篇文档长度之和减去交集并集 |docs[i]| |docs[j]| − 交集相似度取交集与并集之比格式化输出即可单词本身不必再次遍历。该方案还有三个天然正确的特性空文档不会出现在任何倒排列表中枚举时被自然跳过满足忽略空文档的要求交集为空的文档对在cnt中不存在满足只需输出相似度大于 0 的组合倒排列表按编号递增枚举出的编号对已经满足较小者在前无需额外排序。多语言实现与逐行解读仓库在 lcci/17.26.Sparse Similarity 下提供了 Python3、Java、C、Go、TypeScript 五份完整实现对应源码文件分别为 Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts与题解文档中的代码完全一致。Python3class Solution: def computeSimilarities(self, docs: List[List[int]]) - List[str]: eps 1e-9 d defaultdict(list) for i, v in enumerate(docs): for x in v: d[x].append(i) # 倒排索引单词 x - 出现过的文档编号列表递增 cnt Counter() for ids in d.values(): n len(ids) for i in range(n): for j in range(i 1, n): cnt[(ids[i], ids[j])] 1 # 每共现一个单词交集大小加 1 ans [] for (i, j), v in cnt.items(): tot len(docs[i]) len(docs[j]) - v # 并集 长度之和 - 交集 x v / tot eps # 加 eps 修正浮点误差 ans.append(f{i},{j}: {x:.4f}) return ansdefaultdict(list)免去判空逻辑Counter对二元组键计数f-string 的{x:.4f}完成四舍五入到 4 位小数。Javaclass Solution { public ListString computeSimilarities(int[][] docs) { int n docs.length; MapInteger, ListInteger d new HashMap(); for (int i 0; i n; i) { for (int x : docs[i]) { d.computeIfAbsent(x, k - new ArrayList()).add(i); } } MapLong, Integer cnt new HashMap(); for (ListInteger ids : d.values()) { int m ids.size(); for (int i 0; i m; i) { for (int j i 1; j m; j) { long key 1L * ids.get(i) * n ids.get(j); // 编号对编码为单个 long cnt.merge(key, 1, Integer::sum); } } } ListString ans new ArrayList(); for (var e : cnt.entrySet()) { long key e.getKey(); int v e.getValue(); int i (int) (key / n), j (int) (key % n); // 解码还原编号对 int tot docs[i].length docs[j].length - v; double x (double) v / tot 1e-9; ans.add(String.format(%d,%d: %.4f, i, j, x)); } return ans; } }Java 版的关键技巧是键编码由于两个 id 都小于文档总数nkey id1 * n id2是一对一映射一个long即可表示一个编号对。1L *强制以long运算防止溢出500 * 500 250000虽然本例不会溢出但long编码是更稳健的通用写法解码时key / n与key % n无损还原。Cclass Solution { public: vectorstring computeSimilarities(vectorvectorint docs) { using pii pairint, int; double eps 1e-9; unordered_mapint, vectorint d; for (int i 0; i docs.size(); i) { for (int v : docs[i]) { d[v].push_back(i); } } mappii, int cnt; for (auto [_, ids] : d) { int n ids.size(); for (int i 0; i n; i) { for (int j i 1; j n; j) { cnt[{ids[i], ids[j]}]; // pair 直接作为键 } } } vectorstring ans; for (auto [k, v] : cnt) { auto [i, j] k; int tot docs[i].size() docs[j].size() - v; double x (double) v / tot eps; char t[20]; sprintf(t, %d,%d: %0.4lf, i, j, x); ans.push_back(t); } return ans; } };C 版本直接用pairint, int作为map键配合结构化绑定structured bindings读取键值代码紧凑sprintf负责格式化输出。Gofunc computeSimilarities(docs [][]int) []string { d : map[int][]int{} for i, v : range docs { for _, x : range v { d[x] append(d[x], i) } } type pair struct{ i, j int } cnt : map[pair]int{} for _, ids : range d { n : len(ids) for i : 0; i n; i { for j : i 1; j n; j { k : pair{ids[i], ids[j]} cnt[k] } } } ans : []string{} for k, v : range cnt { i, j : k.i, k.j tot : len(docs[i]) len(docs[j]) - v x : float64(v)/float64(tot) 1e-9 ans append(ans, fmt.Sprintf(%d,%d: %.4f, i, j, x)) } return ans }Go 语言通过定义局部pair结构体作为哈希键将id1、id2打包进一个值类型语义清晰。TypeScriptfunction computeSimilarities(docs: number[][]): string[] { const n docs.length; const d new Mapnumber, number[](); for (let i 0; i n; i) { for (const x of docs[i]) { if (!d.has(x)) { d.set(x, []); } d.get(x)!.push(i); } } const cnt new Mapnumber, number(); for (const ids of d.values()) { const m ids.length; for (let i 0; i m; i) { for (let j i 1; j m; j) { const key ids[i] * n ids[j]; // 与 Java 相同的键编码技巧 cnt.set(key, (cnt.get(key) ?? 0) 1); } } } const ans: string[] []; for (const [key, v] of cnt) { const i Math.floor(key / n); const j key % n; const tot docs[i].length docs[j].length - v; const x v / tot 1e-9; ans.push(${i},${j}: ${x.toFixed(4)}); } return ans; }TypeScript 采用与 Java 相同的键编码方案在本题规模ids[i] * n ids[j] ≤ 500 × 500下number完全安全Math.floor(key / n)与key % n还原编号对toFixed(4)完成格式化。关键实现细节剖析编号对的键编码与解码Python/Go 直接用二元组/结构体作键Java/TypeScript 用key id1 * n id2压成单个整数。该编码成立的数学基础是id2 n文档编号范围[0, n)因此乘法编码不存在碰撞除法与取模可无歧义还原。这一技巧在需要以无序编号对为键的算法题中非常通用值得作为模板记忆。浮点精度修正1e-9v / tot在 IEEE 754 浮点除法下可能得到比数学真值略小的结果例如0.1的二进制近似若恰逢格式化边界四舍五入可能产生0.0999而非0.1000。五种实现统一采用x v / tot epseps 1e-9的补偿策略先加一个远小于有效位的微小量再格式化为 4 位小数从而保证舍入结果正确。这是浮点数输出类题目中典型的epsilon 补偿手法。格式化输出的一致性各语言格式化语法不同但语义一致均保留 4 位小数并四舍五入语言格式化方式Python3f-stringf{i},{j}: {x:.4f}JavaString.format(%d,%d: %.4f, i, j, x)Csprintf(t, %d,%d: %0.4lf, i, j, x)Gofmt.Sprintf(%d,%d: %.4f, i, j, x)TypeScript模板字符串 x.toFixed(4)复杂度分析时间复杂度上界为O(m × n²)其中n为文档个数m为单个文档的最大长度每个倒排列表至多两两枚举O(n²)次共m个列表。但题目保证相似度大于 0 的文档对不超过 1000内层循环的实际总次数等于所有文档对交集大小之和因此实际耗时远低于该上界——这正是稀疏特性带来的收益。空间复杂度O(S)S为所有文档的长度之和倒排索引存储全部元素加上cnt中不超过 1000 个有效编号对。正确性论证交集计数正确对任意文档对(a, b)每个同时出现在两篇文档中的单词恰好会让其在倒排列表中对应的编号对(a, b)被枚举一次并计数 1其余单词不会贡献。故cnt[(a, b)]恰为交集大小。并集公式正确文档内元素互不相同集合容斥原理给出|A ∪ B| |A| |B| − |A ∩ B|。输出范围正确cnt中只存在至少共现一个单词的文档对即相似度严格大于 0 的组合空文档不在任何倒排列表内被自动忽略。id 顺序正确倒排列表按文档编号递增写入枚举(ids[i], ids[j])时恒有ids[i] ids[j]键的第一项即为较小 id无需额外比较或排序。延伸思考倒排索引的工程价值本题的三步结构——收集单词到文档的映射、沿倒排列表做配对统计、用统计结果回答问题——是**倒排索引inverted index**这一信息检索核心数据结构的缩影搜索引擎正是预先为每个词维护出现在哪些文档的倒排列表才能在查询时只访问包含关键词的文档子集而无需扫描整个语料库。本题把这一思想压缩进一道面试题中相似度为 0 的文档对不会被任何倒排列表激活计算被天然剪枝交集的规模决定工作量而非全量配对契合稀疏数据的高效处理范式键编码、epsilon 修正等细节则是将算法落到工程输出时的通用素养。从源码结构看doocs/leetcode 仓库将本题收录于 lcci《程序员面试金典第 6 版》系列并标记为困难难度题目侧重考察识别稀疏性并设计针对性数据结构的能力。如果你希望进一步优化还可以思考当交集对数量接近上限 1000 时如何用更紧凑的位图bitset表示文档集合以加速交集计算或者在单词分布极不均匀时先按倒排列表长度排序再配对进一步减少空枚举——这些都是本题自然延伸的优化方向。赞分享示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐LeetCode 面试题 17.26 稀疏相似度基于倒排索引的 Jaccard 相似度算法详解doocs/leetcode 题解LeetCode 面试题 17.26 稀疏相似度基于倒排索引的 Jaccard 相似度算法详解doocs/leetcode 题解 本篇技术指南围绕 doo示例工程教程LeetCode-Go 题解 | 1122. Relative Sort Array相对排序数组的哈希计数与桶排序 Go 实现LeetCode Go 题解 | 1122. Relative Sort Array相对排序数组的哈希计数与桶排序 Go 实现 本篇技术指南以 1122. R示例工程PokemonRedExperiments游戏状态哈希帧相似度计算的高效实现PokemonRedExperiments游戏状态哈希帧相似度计算的高效实现 在强化学习Reinforcement Learning, RL训练《精灵宝可强化学习深度学习AI应用上一篇WAMR pthread 库在 WebAssembly 中启用多线程的完整实战指南下一篇Civitai 付费访问PaidAccess设计开放线程命名、商品边界与价格阶梯的演进决策创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
阅读完成 · 觉得有帮助？
