LC.1912 设计电影租借系统哈希数据结构组合实战核心思想这道题的本质不是算法而是数据结构的组合应用。用 unordered_map 实现 O(1) 定位价格查询用 set 实现自动排序按价格 ID 取前 k状态改变用物理搬运erase insert杜绝遍历关键约束数据量可达 10^5 级任何涉及 O(N) 遍历的操作都会超时。必须保证每个操作都是 O(logN) 或 O(1)。题目描述实现一个电影租借系统MovieRentingSystem(int n, vectorvector entries)初始化entries[i] [shop, movie, price] 表示该商店有该电影的拷贝租金为 price每个商店最多一份该电影。vector search(int movie)返回指定电影当前可租的最便宜 5 个商店按价格升序同价格按商店 ID 升序。void rent(int shop, int movie)租出指定商店的指定电影。void drop(int shop, int movie)归还。vectorvector report()返回全系统已租出的最便宜 5 部电影按价格升序同价格按商店 ID 升序再同商店按电影 ID 升序。数据结构选择classMovieRentingSystem{private:// 1. 未借出索引movie - {price, shop}// 利用 set 自动按 price 升序price 相同按 shop 升序unordered_mapint,setpairint,intunrented;// 2. 价格速查表shop - {movie - price}// 初始化时一次性存好作为后续所有操作的“唯一价格来源”unordered_mapint,unordered_mapint,intpriceMap;// 3. 已借出全局账本{price, {shop, movie}}// set 自动按 price - shop - movie 升序满足 report 要求setpairint,pairint,intrented;public:MovieRentingSystem(intn,vectorvectorintentries);vectorintsearch(intmovie);voidrent(intshop,intmovie);voiddrop(intshop,intmovie);vectorvectorintreport();};方法实现初始化MovieRentingSystem(intn,vectorvectorintentries){for(autoe:entries){intshope[0],moviee[1],pricee[2];unrented[movie].insert({price,shop});priceMap[shop][movie]price;}}search(movie)vectorintsearch(intmovie){vectorintans;if(unrented.count(movie)0)returnans;autosunrented[movie];// 引用避免深拷贝for(autoits.begin();it!s.end()ans.size()5;it){ans.push_back(it-second);// it-second 即 shop}returnans;}rent(shop, movie)voidrent(intshop,intmovie){intpricepriceMap[shop][movie];// O(1) 获取价格unrented[movie].erase({price,shop});// 从未借出集合移除rented.insert({price,{shop,movie}});// 加入已借出账本}drop(shop, movie)voiddrop(intshop,intmovie){intpricepriceMap[shop][movie];rented.erase({price,{shop,movie}});// 从已借出账本移除unrented[movie].insert({price,shop});// 放回未借出集合}report()vectorvectorintreport(){vectorvectorintans;for(autoitrented.begin();it!rented.end()ans.size()5;it){ans.push_back({it-second.first,it-second.second});// {shop, movie}}returnans;}复杂度分析时间复杂度初始化 O(N log M) N 为条目数M 为每部电影平均店铺数search O(5) O(1) 取前 5 个set 内部已排序rent/drop O(log M) O(log R) 各涉及一次 set 删除和一次全局 set 插入/删除report O(5) O(1) 直接取全局有序 set 的前 5 个空间复杂度O(N)存储所有条目。基础加固C 三大容器特性速查1. unordered_map —— 哈希表特性说明底层哈希表有序性无序不保证任何顺序查找/插入/删除平均 O(1)最坏 O(N)键唯一性键不能重复主要用途快速通过键定位值建立索引常用操作unordered_mapint,stringm;m[1]apple;// 插入/覆盖m.insert({2,banana});// 若键已存在则忽略if(m.count(1)){...}// 存在返回 1不存在返回 0不创建空键autoitm.find(2);// 返回迭代器若不存在则为 m.end()m.erase(1);// 按键删除for(auto[k,v]:m){...}// C17 结构化绑定遍历2. set —— 红黑树特性说明底层红黑树平衡二叉搜索树有序性自动按升序排列查找/插入/删除O(log N)元素唯一性元素不能重复主要用途维护自动排序的集合取最值、前 k 个默认排序规则基本类型按 升序。pair先比 first再比 second字典序。自定义类型需重载 operator 或传入比较器。常用操作setpairint,ints;s.insert({3,1});// 自动排序if(s.count({3,1})){...}// 存在返回 1autoits.find({3,1});s.erase({3,1});// 按值删除autosmallest*s.begin();autolargest*s.rbegin();for(autoits.begin();it!s.end()k--;it){...}// 取前 k 个3. pair —— 二元组特性说明定义pairT1, T2成员first类型 T1second类型 T2比较先比 first再比 second主要用途作为 set 或 map 的元素组合多个维度构造方式pairint,stringp1{1,apple};pairint,stringp2make_pair(2,banana);pairint,stringp3(3,cherry);嵌套访问pairint,pairint,intp{5,{1,2}};intap.first;// 5intbp.second.first;// 1intcp.second.second;// 24. 三种结构组合时的排序规则以本题为例组合排序规则setpairint, int先按 first 升序first 相同再按 second 升序setpairint, pairint, int先按最外层 first 升序再按内层 pair 的 first再按内层 secondunordered_mapint, setpairint, int外层无序内层 set 保持有序本题中利用的默认排序unrented[movie] 存 {price, shop} → 自动按价格升序价格相同按商店 ID 升序完美匹配 search 要求。rented 存 {price, {shop, movie}} → 先按价格再按商店再按电影完美匹配 report 要求。5. 性能陷阱与避坑指南陷阱正确做法深拷贝 set用 auto 引用不用 auto 拷贝查询时用 [] 导致插入空键用 count() 或 find() 判断存在性在 set 中按非第一维度删除预先建立辅助索引如 priceMap获取完整键值在 unordered_map 中按值查找键做不到需额外维护反向映射总结核心是数据结构组合哈希表做 O(1) 索引红黑树做自动排序物理搬运代替标记位。严禁遍历数据量大时必须保证每个操作 O(log N) 或 O(1)。状态即容器借出/归还不是改标志位而是把数据从一个容器移到另一个容器。辅助索引是王道用 priceMap 解决“只知道 shop 和 movie需要价格”的痛点。掌握这三种容器的组合用法这道 Hard 题就变成纯粹的代码实现题。