LeetCode 题解工作台
设计电影租借系统
你有一个电影租借公司和 n 个电影商店。你想要实现一个电影租借系统，它支持查询、预订和返还电影的操作。同时系统还能生成一份当前被借出电影的报告。 所有电影用二维整数数组 entries 表示，其中 entries[i] = [shop i , movie i , price i ] 表示商店 sho…
5
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
我们定义一个有序集合 ，其中 存储所有未借出的电影 的商店列表，列表中的元素为 $(\textit{price}, \textit{shop})$，并按照 升序排序，如果 相同，则按照 升序排序。 另外定义一个哈希表 ，其中 $\textit{price\_map}[f(\textit{shop}, \textit{movie})]$ 存储商店 中电影 的租借价格。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
你有一个电影租借公司和 n 个电影商店。你想要实现一个电影租借系统，它支持查询、预订和返还电影的操作。同时系统还能生成一份当前被借出电影的报告。
所有电影用二维整数数组 entries 表示，其中 entries[i] = [shopi, moviei, pricei] 表示商店 shopi 有一份电影 moviei 的拷贝，租借价格为 pricei 。每个商店有 至多一份 编号为 moviei 的电影拷贝。
系统需要支持以下操作：
- Search：找到拥有指定电影且 未借出 的商店中 最便宜的 5 个 。商店需要按照 价格 升序排序，如果价格相同，则
shopi较小 的商店排在前面。如果查询结果少于 5 个商店，则将它们全部返回。如果查询结果没有任何商店，则返回空列表。 - Rent：从指定商店借出指定电影，题目保证指定电影在指定商店 未借出 。
- Drop：在指定商店返还 之前已借出 的指定电影。
- Report：返回 最便宜的 5 部已借出电影 （可能有重复的电影 ID），将结果用二维列表
res返回，其中res[j] = [shopj, moviej]表示第j便宜的已借出电影是从商店shopj借出的电影moviej。res中的电影需要按 价格 升序排序；如果价格相同，则shopj较小 的排在前面；如果仍然相同，则moviej较小 的排在前面。如果当前借出的电影小于 5 部，则将它们全部返回。如果当前没有借出电影，则返回一个空的列表。
请你实现 MovieRentingSystem 类：
MovieRentingSystem(int n, int[][] entries)将MovieRentingSystem对象用n个商店和entries表示的电影列表初始化。List<Integer> search(int movie)如上所述，返回 未借出 指定movie的商店列表。void rent(int shop, int movie)从指定商店shop借出指定电影movie。void drop(int shop, int movie)在指定商店shop返还之前借出的电影movie。List<List<Integer>> report()如上所述，返回最便宜的 已借出 电影列表。
注意：测试数据保证 rent 操作中指定商店拥有 未借出 的指定电影，且 drop 操作指定的商店 之前已借出 指定电影。
示例 1：
输入： ["MovieRentingSystem", "search", "rent", "rent", "report", "drop", "search"] [[3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]], [1], [0, 1], [1, 2], [], [1, 2], [2]] 输出： [null, [1, 0, 2], null, null, [[0, 1], [1, 2]], null, [0, 1]] 解释： MovieRentingSystem movieRentingSystem = new MovieRentingSystem(3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]); movieRentingSystem.search(1); // 返回 [1, 0, 2] ，商店 1，0 和 2 有未借出的 ID 为 1 的电影。商店 1 最便宜，商店 0 和 2 价格相同，所以按商店编号排序。 movieRentingSystem.rent(0, 1); // 从商店 0 借出电影 1 。现在商店 0 未借出电影编号为 [2,3] 。 movieRentingSystem.rent(1, 2); // 从商店 1 借出电影 2 。现在商店 1 未借出的电影编号为 [1] 。 movieRentingSystem.report(); // 返回 [[0, 1], [1, 2]] 。商店 0 借出的电影 1 最便宜，然后是商店 1 借出的电影 2 。 movieRentingSystem.drop(1, 2); // 在商店 1 返还电影 2 。现在商店 1 未借出的电影编号为 [1,2] 。 movieRentingSystem.search(2); // 返回 [0, 1] 。商店 0 和 1 有未借出的 ID 为 2 的电影。商店 0 最便宜，然后是商店 1 。
提示：
1 <= n <= 3 * 1051 <= entries.length <= 1050 <= shopi < n1 <= moviei, pricei <= 104- 每个商店 至多 有一份电影
moviei的拷贝。 search，rent，drop和report的调用 总共 不超过105次。
解题思路
方法一：有序集合
我们定义一个有序集合 ，其中 存储所有未借出的电影 的商店列表，列表中的元素为 ，并按照 升序排序，如果 相同，则按照 升序排序。
另外定义一个哈希表 ，其中 存储商店 中电影 的租借价格。
我们还定义一个有序集合 ，其中存储所有已借出的电影，元素为 ，并按照 升序排序，如果 相同，则按照 升序排序，如果 也相同，则按照 升序排序。
对于 操作，我们遍历 ，将每个商店的电影信息加入到 和 中。时间复杂度为 ，其中 是 的长度。
对于 操作，我们返回 中前 5 个商店的编号。时间复杂度为 。
对于 操作，我们从 中移除 ，并将 加入到 中。时间复杂度为 。
对于 操作，我们从 中移除 ，并将 加入到 中。时间复杂度为 。
对于 操作，我们返回 中前 5 个已借出电影的商店编号和电影编号。时间复杂度为 。
空间复杂度为 。其中 是 的长度。
class MovieRentingSystem:
def __init__(self, n: int, entries: List[List[int]]):
self.available = defaultdict(lambda: SortedList())
self.price_map = {}
for shop, movie, price in entries:
self.available[movie].add((price, shop))
self.price_map[self.f(shop, movie)] = price
self.rented = SortedList()
def search(self, movie: int) -> List[int]:
return [shop for _, shop in self.available[movie][:5]]
def rent(self, shop: int, movie: int) -> None:
price = self.price_map[self.f(shop, movie)]
self.available[movie].remove((price, shop))
self.rented.add((price, shop, movie))
def drop(self, shop: int, movie: int) -> None:
price = self.price_map[self.f(shop, movie)]
self.rented.remove((price, shop, movie))
self.available[movie].add((price, shop))
def report(self) -> List[List[int]]:
return [[shop, movie] for _, shop, movie in self.rented[:5]]
def f(self, shop: int, movie: int) -> int:
return shop << 30 | movie
# Your MovieRentingSystem object will be instantiated and called as such:
# obj = MovieRentingSystem(n, entries)
# param_1 = obj.search(movie)
# obj.rent(shop,movie)
# obj.drop(shop,movie)
# param_4 = obj.report()
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the number of movies and shops and the efficiency of maintaining sorted sets. Search, rent, and drop are roughly O(log m) per operation using ordered sets, where m is number of copies of a movie. Space complexity depends on storing availability sets and rented lists, proportional to entries length. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if your solution maintains correct ordering when multiple shops have same price.
- question_mark
Ensure that search, rent, drop, and report operations all meet performance requirements under 10^5 calls.
- question_mark
Consider whether using built-in sorted structures or custom heaps impacts efficiency and correctness.
常见陷阱
外企场景- error
Failing to sort shops correctly in search when prices tie, leading to wrong shop order.
- error
Updating availability and rented sets incorrectly when a movie is rented or returned.
- error
Assuming each shop can hold multiple copies of the same movie, which violates constraints.
进阶变体
外企场景- arrow_right_alt
Add support for bulk rentals and returns where multiple copies are rented or dropped at once.
- arrow_right_alt
Track popularity of movies to generate a report of most rented movies instead of cheapest.
- arrow_right_alt
Extend to handle dynamic price updates while preserving search and report order.