1. 第三篇的“其他”到底指哪一类结构1.1 前两篇划过的边界先简单对齐这系列做到第三篇手感比刚开始顺了不少。前两篇把数组、链表、二叉树这些需要自己动手磨的结构基本过了一遍到这一篇标题里的“其他数据结构”其实是一个信号必须手写实现的部分已经告一段落后面的对手是 Rust 标准库里早就封装好的容器族——HashMap、BTreeMap、HashSet、BTreeSet、BinaryHeap、VecDeque。换句话说考察重心从“怎么把结构造出来”挪到了“怎么把结构选对、用熟”上。很多从 C 转过来的朋友会下意识去找“Rust 版的 map、set、priority_queue”然后发现名字差不多但用起来处处受所有权和 trait 的约束。有人干脆自己撸一个数据结构结果代码越写越长调试时间翻倍。我的建议很直接OJ 题比赛的是算法正确性和复杂度不是内存布局表演。除了并查集这种标准库确实没有的结构以及少数被常数逼到墙角的情况你几乎没有理由在 OJ 上徒手重写二叉堆或哈希表。这一篇的目标读者分两类。一类是刚把 Rust 语法啃完、打算拿 OJ 练手的初学者你需要的是“什么场景对应什么容器”的判断模型另一类是已经写过几道题、但总在借用检查器面前卡住的人这篇会重点讲那些最容易翻车的 API 用法和边界条件。两种需求都覆盖到读完你至少能把标准容器在 OJ 里的常规姿势直接抄走。1.2 标准库优先手写兜底做 OJ 题时我脑中有一套选择顺序基本是倒着来的第一问能不能用Vec加排序搞定第二问需不需要“某个值是否存在”这类 O(1) 查询第三问需不需要实时知道当前最大或最小第四问需不需要维护一个有序集合并且经常做“找前驱、找后继”这种操作这四问下来80% 的数据结构题已经落在标准库范围内了。只有两种情况我会考虑手写一种是并查集、单调队列、Trie、Segment Tree 这类标准库没提供、但题目明摆着要你自建的结构另一种是像哈希表被针对性卡死这种极少见的场景得换自写哈希或调整策略。平时把标准库用对复杂度是明牌HashMap 均摊 O(1)BTreeMap 严格 O(log n)BinaryHeap 进出堆 O(log n)VecDeque 头尾操作 O(1)。这些复杂度在 OJ 里足够你估算出能不能过而不必陷入实现细节的泥潭。2. 先盘点 Rust 容器家族它们各自解决什么问题2.1 键值映射HashMap 与 BTreeMapHashMap和BTreeMap都存键值对但底层模型完全不同。HashMap 是无序的靠哈希函数把键映射到桶里适合“我只想立刻知道 key 对应的 value 是什么”的场景比如统计频率、记录出现位置、记忆化搜索。BTreeMap 底层是 B 树键始终有序适合“我需要按键从小到大遍历、取前驱后继、做区间查询”的场景。选择时有一条很实用的经验**如果题目输出不要求排序优先 HashMap一旦涉及有序输出、求最接近的键、按范围统计就换 BTreeMap。**比如“给定若干区间合并后输出有序结果”你当然可以把区间丢进 Vec 排序再合并但如果你需要边插入边保持有序BTreeMap 更顺手。另外注意 trait 约束HashMap 要求键实现Hash EqBTreeMap 要求键实现Ord。基本类型和 String 都满足但自定义结构体要想当键得自己 derive 或实现这些 trait。Rust 的 HashMap 默认用 SipHash 作为哈希算法带随机种子。好处是能防御针对哈希表的碰撞攻击坏处是常数比简单哈希稍大。OJ 上绝大多数题目感知不到这个差距但如果你发现某道哈希题整体算法正确却超时确实可以怀疑一下这里。真要优化别一上来就换自定义哈希先确认是不是数据量或者死循环问题。后续我会在踩坑部分展开。2.2 集合HashSet 与 BTreeSetHashSet 和 BTreeSet 可以理解成只关心键、不关心值的 HashMap 和 BTreeMap。问题里只要出现“这个元素出现过没有”“哪些元素不重复”这类诉求就用HashSet。如果还要求“把不重复元素按顺序输出”或“找到比 x 大的最小元素”就用BTreeSet。这里有个新手容易忽略的点Rust 的 HashSet 本身支持集合运算比如union、intersection、difference、symmetric_difference返回的是迭代器。OJ 里遇到“两个数组的交集”“统计两个集合的差异”这类题如果直接用这些方法代码量小逻辑也清晰。需要注意返回的是迭代器得.collect()到 Vec 或直接遍历而且迭代器的顺序依然受底层结构影响HashSet 别依赖顺序BTreeSet 可以。2.3 特殊队列BinaryHeap 与 VecDequeBinaryHeap 在 Rust 里默认是最大堆peek()和pop()拿到的都是堆里最大的元素。很多算法题需要的恰恰是“始终取最小”这时候标准解法是套一层Reverse也就是BinaryHeapReverseT。这个细节单独拆出来讲因为它是 Rust 做题时最容易栽进去的坑之一。后面第三部分和第四部分都会反复用到。VecDeque 是双端队列头部和尾部都能 O(1) 进出。它的地位在 OJ 里经常被低估BFS 需要队列滑动窗口需要维护窗口内最大最小值这些场景VecDeque比Vec更合适。用Vec做队列时remove(0)是 O(n) 的数据一大就超时。许多人 debug 阶段没感觉换大数据就崩根源就在这里。我用 VecDeque 时习惯只记住四个方法push_back、pop_front、push_front、pop_back足以覆盖绝大多数滑动窗口和 BFS 场景。2.4 一张表把区别说清楚| 容器 | 底层结构 | 是否有序 | 键/元素唯一 | 核心操作复杂度 | 典型场景 | | --- | --- | --- | --- | --- | | HashMap | 哈希表 | 否 | 键唯一 | 均摊 O(1) | 计数、映射、缓存 | | BTreeMap | B 树 | 是 | 键唯一 | O(log n) | 有序键、区间查询、前驱后继 | | HashSet | 哈希表 | 否 | 元素唯一 | 均摊 O(1) | 去重、存在性检查 | | BTreeSet | B 树 | 是 | 元素唯一 | O(log n) | 有序集合、范围遍历 | | BinaryHeap | 二叉堆 | 部分堆序 | 可重复 | 插入/弹出 O(log n) | 最大最小优先队列 | | VecDeque | 双端队列 | 否 | 可重复 | 头尾 O(1) | 队列、BFS、滑动窗口 |这张表不是让你背下来而是做题时对照着用。看到“最大”“最小”“前 K 个”就往 BinaryHeap 想看到“是否出现过”“统计次数”就往 HashMap 想看到“有序”“区间”就往 BTree 系列想看到“一层一层扩展”“窗口往右滑”就往 VecDeque 想。表格是地图不是考试大纲。3. 做题前先背下来的三个高频套路3.1 计数与 TopKHashMap 的 entry 接口统计频率是 OJ 的常客。C 选手写unordered_mapint,int cnt; cnt[x];特别自然但 Rust 的 HashMap 只提供了只读索引没有赋值索引所以map[x] 1是编译不过的。正确姿势是用entry接口use std::collections::HashMap; fn count_words(text: str) - HashMapstr, i32 { let mut cnt HashMap::new(); for word in text.split_whitespace() { cnt.entry(word) .and_modify(|c| *c 1) .or_insert(1); } cnt }这里entry(word)返回的是枚举Entryand_modify负责“如果键已存在就对值做闭包操作”or_insert负责“如果键不存在就插入默认值”。新手最爱写的or_insert(0)配合解引用递增也可以*cnt.entry(word).or_insert(0) 1;两种写法等效前者更明确后者更短。说实话我在 OJ 上多数时候用后者因为少写几行。要明白的是entry返回的是一个“借用了 map 的可变引用”的枚举所以一定要在同一个表达式里完成修改拆成两行容易触发借用冲突。光会统计还不够题目经常让输出出现次数最多的前 K 个元素。这时就需要堆登场。先把所有键值对放进BinaryHeap因为元组默认先比较第一个元素所以把(次数, 元素)压进去每次pop拿到的就是“次数最多且元素值最大”的那一项。如果希望次数相同时按元素升序输出就得在这个元组上动点手脚或者直接用最小堆维护前 K 个这部分我在第四题里给完整代码。3.2 逐层扩展VecDeque 的入队出队姿势BFS广度优先搜索是图论和网格题的基础。Rust 里实现 BFS 的标准姿势是VecDeque 一个visited记录。网格题里常见的是“从某个位置出发能扩展到哪些相邻位置”。这里有两个新手坑一是坐标类型数组下标是 usize做加减法时容易越界要用 isize 或者显式判断边界二是标记访问的时机应该在入队时立刻标记而不是在弹出时才标记否则同一个坐标会被重复入队很多次直接超时。写对 BFS 队列的要点只有三个push_back放新节点pop_front取当前节点入队同时标记。不要用Vec remove(0)那是灾难性的 O(n) 操作数据规模一大光这个就会让复杂度从 O(rowscols) 膨胀成 O(rowscolsrowscols)。3.3 有序维护BTreeSet 的 range 查询BTreeSet和BTreeMap在 OJ 里最漂亮的能力是有序和范围查询。比如“给定一个集合反复插入和删除整数每次问大于等于 x 的最小值是多少”没有有序容器就得每次排序有了 BTreeSet 就完全不同use std::collections::BTreeSet; fn main() { let mut set BTreeSet::new(); set.insert(3); set.insert(7); set.insert(12); if let Some(v) set.range(5..).next() { println!( 5 的最小值是 {}, v); } if let Some(v) set.range(..7).next_back() { println!( 7 的最大值是 {}, v); } }range(5..)是左闭右开区间表示从 5 开始到无穷range(..7)是左负无穷到 7 的闭区间。next()拿区间里第一个元素next_back()拿最后一个正好对应“后继”和“前驱”两种查询。还有range(3..8)这种标准范围写法。这类模板在处理“有序插入 查询相邻元素”的问题时极其好用比如日程安排、区间插入、最近可用编号等。如果你想维护的是键值对而不是简单元素那就用BTreeMap它也有同样的range方法返回的是(键, 值)迭代器。4. 三道 OJ 原题级拆解从读入到输出4.1 前 K 个高频元素HashMap BinaryHeap 组合题目做完简单复盘“给定 n 个整数和一个 k输出出现次数最多的 k 个数。”我按 OJ 常见输入格式处理第一行是n k第二行是 n 个数。完整代码如下use std::collections::{BinaryHeap, HashMap}; use std::io::{self, Read}; fn solve(input: str) - String { let mut it input.split_whitespace().map(|s| s.parse::i32().unwrap()); let n it.next().unwrap() as usize; let k it.next().unwrap() as usize; let mut cnt HashMap::new(); for _ in 0..n { let x it.next().unwrap(); *cnt.entry(x).or_insert(0) 1; } let mut heap BinaryHeap::new(); for (num, c) in cnt { heap.push((c, num)); } let mut ans Vec::new(); for _ in 0..k { if let Some((_, num)) heap.pop() { ans.push(num.to_string()); } } ans.join( ) } fn main() { let mut input String::new(); io::stdin().read_to_string(mut input).unwrap(); println!({}, solve(input)); }为什么heap.push((c, num))而不是(num, c)因为 BinaryHeap 默认最大堆元组比较先看第一个字段。如果先放num再放c堆顶就会变成“数值最大的元素”而不是“次数最多的元素”整道题就错了。这个顺序问题值得反复强调真有人在这里栽过。复杂度上统计一遍是 O(n)把所有(次数, 元素)全部入堆是 O(m log m)m 是不同元素的个数。如果 k 远小于 m可以改进为维护一个大小为 k 的最小堆每个新元素和堆顶比较堆顶是最小次数这样复杂度变成 O(m log k)空间也小。需要取最小堆时把BinaryHeap(Reverseu32, ...)或者直接包一层Reverse按需求做。但多数题目 m 不大全量入堆也能过写起来反而简单。4.2 合并 K 个有序数组Reverse 包一层的堆这个问题的 OJ 版本通常长这样给 K 个升序数组合并成一个升序数组。朴素做法是把所有元素装进一个 Vec 再排序复杂度是 O(total log total)听起来也不是不行但问题往往是“K 较大、每个数组较长”面试和 OJ 真正想考的其实是多路归并利用每路都有序的特性用优先队列每次选出当前最小的“队头”。核心代码use std::cmp::Reverse; use std::collections::BinaryHeap; fn merge_k_sorted(arrs: [Veci32]) - Veci32 { let mut heap BinaryHeap::new(); for (arr_id, arr) in arrs.iter().enumerate() { if let Some(first) arr.first() { heap.push(Reverse((first, arr_id, 0))); } } let mut result Vec::new(); while let Some(Reverse((val, arr_id, idx))) heap.pop() { result.push(val); if idx 1 arrs[arr_id].len() { heap.push(Reverse((arrs[arr_id][idx 1], arr_id, idx 1))); } } result }这里Reverse是整个元组包进去的不是只包值。这么做的原因是堆里比较时按元组顺序比较先看数值数值相同再看数组编号再相同看下标。三个字段顺序很讲究(val, arr_id, idx)保证堆顶永远是当前所有数组中“最小的那个值”如果把arr_id放最前面堆顶会变成“编号最大的数组的最小值”那可就错了。整个思路是每个数组先各取第一个元素入堆弹出最小的那个后从同一个数组里继续取下一位补进去。就像 K 路队伍各自报数你每次喊最小号的出列然后让那个队伍补下一个数字直到所有队伍都空了。整个过程每个元素入堆一次、弹出一次复杂度 O(total log K)比“全排完”优雅得多。4.3 岛屿数量网格 BFS 中 VecDeque 和原地标记岛屿数量是另一个高频题二维字符矩阵里1表示陆地0表示水上下左右相邻的1算同一个岛屿问有几个岛。思路也很标准遍历每个格子遇到没访问过的陆地就把它当成新岛屿然后从它开始 BFS把整个岛屿全部标记为已访问。为了省掉额外的 visited 数组我选择原地把访问过的陆地改成0等价于“淹掉这个岛”。use std::collections::VecDeque; fn num_islands(mut grid: VecVecchar) - i32 { let rows grid.len(); let cols grid[0].len(); let mut count 0; for i in 0..rows { for j in 0..cols { if grid[i][j] ! 1 { continue; } count 1; grid[i][j] 0; let mut queue VecDeque::new(); queue.push_back((i, j)); while let Some((r, c)) queue.pop_front() { for (dr, dc) in [(1, 0), (-1, 0), (0, 1), (0, -1)] { let nr r as isize dr; let nc c as isize dc; if nr 0 || nr rows as isize { continue; } if nc 0 || nc cols as isize { continue; } let nr nr as usize; let nc nc as usize; if grid[nr][nc] 1 { grid[nr][nc] 0; queue.push_back((nr, nc)); } } } } } count }这段代码里最关键的是“在入队时立刻把陆地改成0”。如果改成“弹出时才标记”同一个格子可能被周围四个格子重复入队队列里会有大量重复元素最坏情况能直接打爆时间。我见过不少人在这道题上 TLE就是因为少了这一句话。另一个细节是坐标计算r和c是 usize不能直接减 1所以先as isize做加减判断完边界后再转会 usize。这个 isize 往返看着有点啰嗦但在二维网格题里是标准防御姿势写习惯了就不觉得麻烦。上面三道题覆盖了 HashMap、BinaryHeap、Reverse、VecDeque 四个最常用的容器组合。题目本身不是难点难点是把每个结构放在它最合适的位置计数用 HashMap优先级用堆逐层扩散用队列。剩下的 BTree 系列我放到了前面的模板里你遇到“有序 区间”题时直接套。5. 实战里最容易翻车的几个点5.1 所有权和借用不是 C 的引用Rust 做题最大的心智负担就是借用检查器。最常见的一句报错是cannot borrow cnt as mutable because it is also borrowed as immutable基本都出现在“遍历一个容器时又试图修改它”。比如你想统计完再顺手清理某个键写出类似这样的代码let mut cnt HashMap::new(); // 中间省略 for (k, v) in cnt.iter() { if v 1 { cnt.remove(k); // 编译错误不可变借用和可变借用同时存在 } }这种写法 C 里没事Rust 里就是不行。OJ 场景下我的处理办法很简单先遍历收集需要删除或修改的键到临时 Vec再根据这个 Vec 去操作原容器。多一次遍历通常不影响复杂度但把借用的痛苦降到最低。记住一个心智模型iter()会把整个容器“借”给你你在借期内不能做任何可变操作。想边遍历边修改时问问自己“能不能分两步做”。还有一种很常见的场景是“遍历数组同时更新 HashMap”。数组本身在 for 循环里默认按值取如果你需要索引又需要修改 map最好这样写for (i, x) in nums.iter().enumerate() { // i 是索引x 是 i32 map.insert(*x, i); }这里nums.iter()借的是 numsmap.insert借的是 map两个对象不同不会冲突。所以很多时候不是不能改是别在同一个容器上同时做不可变迭代和可变写入。5.2 BinaryHeap 的默认方向为什么总看到 ReverseBinaryHeap默认是最大堆这跟很多算法竞赛选手用惯的最小堆正好反着。解决方式不是自己写一个最小堆而是包装Reverse。Reverse会把元素的比较结果翻转放进堆里之后堆顶反而是“按原比较规则最小”的元素。很多人一开始不知道能这么干硬是手写堆其实标准库已经给你留了后门。不过Reverse不是万能的。它要求内部类型实现Ord。对于整数、字符串、元组这些类型没问题但如果你创建了自己的结构体就需要手动实现PartialOrd、Ord、PartialEq、Eq四个 trait 才能塞进 BinaryHeap。我的建议是做题时尽量用元组而不是自定义结构体。比如堆元素需要三个字段时直接用(i32, usize, usize)配合Reverse玩顺序比写结构体再 impl 一堆 trait 省心得多。还有一个小细节当你只想取“当前最大值但不想弹出”用peek()它返回OptionT。如果你对这个引用修改就需要注意借用问题。OJ 里多数场景是“先 peek 比较再 pop”这两步分开写就没问题。5.3 读入和输出的习惯姿势OJ 上 Rust 读入不要用read_line一行行拼那很慢且容易写乱。我长期用的是use std::io::{self, Read}; fn main() { let mut input String::new(); io::stdin().read_to_string(mut input).unwrap(); // 把 input 交给 solve 函数处理 }这样会把所有输入一次性读进一个字符串然后split_whitespace()加parse()既能应对跨行输入也不会被空白符干扰。解析整数时可以用习惯的 chaininput.split_whitespace().map(|s| s.parse::i64().unwrap())把结果当成一个迭代器一个个取。这个技巧在题目第一行给 n、后面给 n 行数据时尤其好用因为你不必维护“当前读了几行”的状态。输出方面最容易忽略的是顺序问题。HashMap 迭代顺序不保证所以凡是输出要求按原始顺序或按值排序的结果必须先把结果整理进 Vec 排序再用 join 拼接。我见过有人直接遍历 HashMap 输出本地跑没问题一提交就 Wrong Answer原因就是随机种子让每次运行顺序都不一样。既然输出不稳定正确性当然无从谈起。5.4 性能上容易被忽略的小开销标准库容器在算法正确的前提下很少拖后腿但有几个小开销还是值得注意。第一HashMap的默认哈希是 SipHash随机种子让每次程序运行哈希分布都不一样理论上能防碰撞攻击常数也比简单哈希慢。OJ 数据一般是静态构造的不太可能刻意卡你但我真遇到过一道“数据量大到 HashMap 过不了”的题换成排序 双指针直接过了。所以遇到哈希超时不要死磕HashMap考虑一下能否用排序换掉它。第二String 做键尽量用str借用避免多余的克隆。比如HashMapstr, i32在遍历时会借入而不是复制整个字符串。如果键的所有权来自输入字符串用借用关系既能过编译又少一次分配。不过注意生命周期HashMap 存活期间借用来源的 String 不能提前销毁。理解这一点之后你会少很多“为什么不让我用 HashMapstr, _”的疑问。第三提前设置容量。能预估数据量时用Vec::with_capacity(n)、HashMap::with_capacity(n)可以减少扩容时反复分配内存。扩容虽然均摊 O(1)但常数也不小在大数据面前能省一点是一点。6. 关于“数据结构题”我自己的一些体会做这一系列题最大的收获不是背会了哪个 API而是慢慢建立起一种“判断模型”每个题目陈述里的关键词都在暗示你应该用哪种结构。“出现次数”指向 HashMap“前 K 大”指向堆“覆盖区间”指向排序或 BTree“上下左右扩散”指向 BFS 队列。把这些信号识别出来剩下的就是把模板填进去。我也有一些固执的小习惯。比如能用排序解决的题我不会优先考虑复杂的平衡树能用Vec干完的事不会为了炫技上 HashMap堆里能塞元组就绝不自定义结构体。这些选择不是“正确”而是省时间、少 debug、降低心智负担。OJ 实战到了一定阶段比的不是谁会的结构多而是谁在正确的地方选择正确的结构并且能一次写对。这套“其他数据结构”的模板我个人是从第三篇开始真正找到感觉的希望你也能顺着这几个套路把手里的题刷明白。