Hard

题目描述

你有一个由 n 个商店组成的电影租赁公司。你想实现一个租赁系统，支持搜索、预订和归还电影。该系统还应支持生成当前租赁电影的报告。

每部电影作为二维整数数组 entries 给出，其中 entries[i] = [shopi, moviei, pricei] 表示商店 shopi 有一份电影 moviei 的拷贝，租赁价格为 pricei。每个商店最多有一份电影 moviei 的拷贝。

系统应支持以下功能：

  • 搜索：找到有给定电影未租赁拷贝的最便宜的 5 个商店。商店应按价格升序排序，如果价格相同，shopi 较小的应排在前面。如果匹配的商店少于 5 个，则应返回所有匹配的商店。如果没有商店有未租赁的拷贝，则应返回空列表。
  • 租赁：从给定商店租赁给定电影的未租赁拷贝。
  • 归还：在给定商店归还之前租赁的给定电影拷贝。
  • 报告：返回最便宜的 5 部已租赁电影（可能是相同的电影 ID）作为二维列表 res，其中 res[j] = [shopj, moviej] 描述第 j 便宜的已租赁电影 moviej 是从商店 shopj 租赁的。res 中的电影应按价格升序排序，如果价格相同，shopj 较小的应排在前面，如果仍然相同，moviej 较小的应排在前面。如果已租赁电影少于 5 部，则应返回所有电影。如果当前没有电影被租赁，则应返回空列表。

实现 MovieRentingSystem 类：

  • MovieRentingSystem(int n, int[][] entries) 用 n 个商店和 entries 中的电影初始化 MovieRentingSystem 对象。
  • List<Integer> search(int movie) 返回如上所述拥有给定电影未租赁拷贝的商店列表。
  • void rent(int shop, int movie) 从给定商店租赁给定电影。
  • void drop(int shop, int movie) 在给定商店归还之前租赁的电影。
  • List<List<Integer>> report() 返回如上所述的最便宜已租赁电影列表。

示例 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]]

约束条件：

  • 1 <= n <= 3 * 10^5
  • 1 <= entries.length <= 10^5
  • 0 <= shopi < n
  • 1 <= moviei, pricei <= 10^4
  • 每个商店最多有一份电影 moviei 的拷贝
  • 对 search、rent、drop 和 report 的调用总数最多为 10^5

解题思路

这道题需要设计一个电影租赁系统，核心在于维护两种状态：未租赁和已租赁的电影，并能快速进行查询和更新操作。

解题思路：

  1. 数据结构设计：

    • 使用哈希表 unrented 按电影ID分组存储未租赁的电影，每组使用有序集合维护按价格和商店ID排序的电影
    • 使用有序集合 rented 存储已租赁的电影，按价格、商店ID、电影ID排序
    • 使用哈希表 price 存储每个(商店,电影)对应的价格，便于快速查找

  2. 操作实现：

    • search：从对应电影ID的有序集合中取前5个元素
    • rent：从未租赁集合中删除，加入已租赁集合
    • drop：从已租赁集合中删除，加入未租赁集合
    • report：从已租赁集合中取前5个元素

  3. 排序规则：

    • 未租赁：按(价格, 商店ID)排序
    • 已租赁：按(价格, 商店ID, 电影ID)排序

使用有序集合（C++中的set，Python中的SortedSet）能保证插入、删除、查询操作的时间复杂度都是O(log n)，满足题目的性能要求。

推荐解法：使用哈希表+有序集合的组合，既能快速定位又能维护有序性。

代码实现

class MovieRentingSystem {
private:
    unordered_map<int, set<pair<int, int>>> unrented; // movie -> {(price, shop)}
    set<tuple<int, int, int>> rented; // {(price, shop, movie)}
    unordered_map<int, unordered_map<int, int>> price; // shop -> movie -> price

public:
    MovieRentingSystem(int n, vector<vector<int>>& entries) {
        for (auto& entry : entries) {
            int shop = entry[0], movie = entry[1], p = entry[2];
            unrented[movie].insert({p, shop});
            price[shop][movie] = p;
        }
    }
    
    vector<int> search(int movie) {
        vector<int> result;
        if (unrented.find(movie) == unrented.end()) return result;
        
        int count = 0;
        for (auto& [p, shop] : unrented[movie]) {
            if (count >= 5) break;
            result.push_back(shop);
            count++;
        }
        return result;
    }
    
    void rent(int shop, int movie) {
        int p = price[shop][movie];
        unrented[movie].erase({p, shop});
        rented.insert({p, shop, movie});
    }
    
    void drop(int shop, int movie) {
        int p = price[shop][movie];
        rented.erase({p, shop, movie});
        unrented[movie].insert({p, shop});
    }
    
    vector<vector<int>> report() {
        vector<vector<int>> result;
        int count = 0;
        for (auto& [p, shop, movie] : rented) {
            if (count >= 5) break;
            result.push_back({shop, movie});
            count++;
        }
        return result;
    }
};

from sortedcontainers import SortedSet
from typing import List

class MovieRentingSystem:

    def __init__(self, n: int, entries: List[List[int]]):
        self.unrented = {}  # movie -> SortedSet of (price, shop)
        self.rented = SortedSet()  # SortedSet of (price, shop, movie)
        self.price = {}  # shop -> movie -> price
        
        for shop, movie, p in entries:
            if movie not in self.unrented:
                self.unrented[movie] = SortedSet()
            self.unrented[movie].add((p, shop))
            
            if shop not in self.price:
                self.price[shop] = {}
            self.price[shop][movie] = p

    def search(self, movie: int) -> List[int]:
        if movie not in self.unrented:
            return []
        
        result = []
        for i, (p, shop) in enumerate(self.unrented[movie]):
            if i >= 5:
                break
            result.append(shop)
        return result

    def rent(self, shop: int, movie: int) -> None:
        p = self.price[shop][movie]
        self.unrented[movie].remove((p, shop))
        self.rented.add((p, shop, movie))

    def drop(self, shop: int, movie: int) -> None:
        p = self.price[shop][movie]
        self.rented.remove((p, shop, movie))
        self.unrented[movie].add((p, shop))

    def report(self) -> List[List[int]]:
        result = []
        for i, (p, shop, movie) in enumerate(self.rented):
            if i >= 5:
                break
            result.append([shop, movie])
        return result

public class MovieRentingSystem {
    private Dictionary<int, SortedSet<(int price, int shop)>> unrented;
    private SortedSet<(int price, int shop, int movie)> rented;
    private Dictionary<int, Dictionary<int, int>> price;

    public MovieRentingSystem(int n, int[][] entries) {
        unrented = new Dictionary<int, SortedSet<(int, int)>>();
        rented = new SortedSet<(int, int, int)>();
        price = new Dictionary<int, Dictionary<int, int>>();
        
        foreach (var entry in entries) {
            int shop = entry[0], movie = entry[1], p = entry[2];
            
            if (!unrented.ContainsKey(movie)) {
                unrented[movie] = new SortedSet<(int, int)>();
            }
            unrented[movie].Add((p, shop));
            
            if (!price.ContainsKey(shop)) {
                price[shop] = new Dictionary<int, int>();
            }
            price[shop][movie] = p;
        }
    }
    
    public IList<int> Search(int movie) {
        var result = new List<int>();
        if (!unrented.ContainsKey(movie)) return result;
        
        int count = 0;
        foreach (var (p, shop) in unrented[movie]) {
            if (count >= 5) break;
            result.Add(shop);
            count++;
        }
        return result;
    }
    
    public void Rent(int shop, int movie) {
        int p = price[shop][movie];
        unrented[movie].Remove((p, shop));
        rented.Add((p, shop, movie));
    }
    
    public void Drop(int shop, int movie) {
        int p = price[shop][movie];
        rented.Remove((p, shop, movie));
        unrented[movie].Add((p, shop));
    }
    
    public IList<IList<int>> Report() {
        var result = new List<IList<int>>();
        int count = 0;
        foreach (var (p, shop, movie) in rented) {
            if (count >= 5) break;
            result.Add(new List<int> { shop, movie });
            count++;
        }
        return result;
    }
}

var MovieRentingSystem = function(n, entries) {
    this.unrented = new Map(); // movie -> array of [price, shop]
    this.rented = []; // array of [price, shop, movie]
    this.price = new Map(); // shop -> Map(movie -> price)
    
    for (let [shop, movie, p] of entries) {
        if (!this.unrented.has(movie)) {
            this.unrented.set(movie, []);
        }
        this.unrented.get(movie).push([p, shop]);
        
        if (!this.price.has(shop)) {
            this.price.set(shop, new Map());
        }
        this.price.get(shop).set(movie, p);
    }
    
    // Sort unrented movies for each movie ID
    for (let [movie, shops] of this.unrented) {
        shops.sort((a, b) => a[0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
构造函数O(E log E)O(E)
searchO(1)O(1)