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;
    }
}

class MinHeap {
    constructor(compare) {
        this.data = [];
        this.compare = compare;
    }

    size() {
        return this.data.length;
    }

    peek() {
        return this.data[0];
    }

    push(value) {
        this.data.push(value);
        let index = this.data.length - 1;
        while (index > 0) {
            const parent = Math.floor((index - 1) / 2);
            if (this.compare(this.data[parent], this.data[index]) <= 0) {
                break;
            }
            [this.data[parent], this.data[index]] = [this.data[index], this.data[parent]];
            index = parent;
        }
    }

    pop() {
        const top = this.data[0];
        const last = this.data.pop();
        if (this.data.length > 0) {
            this.data[0] = last;
            let index = 0;
            while (true) {
                let smallest = index;
                const left = index * 2 + 1;
                const right = left + 1;
                if (left < this.data.length && this.compare(this.data[left], this.data[smallest]) < 0) {
                    smallest = left;
                }
                if (right < this.data.length && this.compare(this.data[right], this.data[smallest]) < 0) {
                    smallest = right;
                }
                if (smallest === index) {
                    break;
                }
                [this.data[index], this.data[smallest]] = [this.data[smallest], this.data[index]];
                index = smallest;
            }
        }
        return top;
    }
}

var MovieRentingSystem = function(n, entries) {
    this.available = new Map();
    this.rented = new MinHeap((a, b) => a[0] - b[0] || a[1] - b[1] || a[2] - b[2]);
    this.prices = new Map();
    this.versions = new Map();
    this.rentedKeys = new Set();

    for (const [shop, movie, price] of entries) {
        if (!this.available.has(movie)) {
            this.available.set(movie, new MinHeap((a, b) => a[0] - b[0] || a[1] - b[1]));
        }
        const key = `${shop},${movie}`;
        this.prices.set(key, price);
        this.versions.set(key, 0);
        this.available.get(movie).push([price, shop, 0]);
    }
};

MovieRentingSystem.prototype.search = function(movie) {
    const heap = this.available.get(movie);
    if (!heap) {
        return [];
    }

    const selected = [];
    while (selected.length < 5) {
        while (heap.size() > 0) {
            const [price, shop, version] = heap.peek();
            const key = `${shop},${movie}`;
            if (!this.rentedKeys.has(key) && this.versions.get(key) === version) {
                break;
            }
            heap.pop();
        }
        if (heap.size() === 0) {
            break;
        }
        selected.push(heap.pop());
    }

    for (const entry of selected) {
        heap.push(entry);
    }
    return selected.map((entry) => entry[1]);
};

MovieRentingSystem.prototype.rent = function(shop, movie) {
    const key = `${shop},${movie}`;
    const version = this.versions.get(key) + 1;
    this.versions.set(key, version);
    this.rentedKeys.add(key);
    this.rented.push([this.prices.get(key), shop, movie, version]);
};

MovieRentingSystem.prototype.drop = function(shop, movie) {
    const key = `${shop},${movie}`;
    const version = this.versions.get(key) + 1;
    this.versions.set(key, version);
    this.rentedKeys.delete(key);
    this.available.get(movie).push([this.prices.get(key), shop, version]);
};

MovieRentingSystem.prototype.report = function() {
    const selected = [];
    while (selected.length < 5) {
        while (this.rented.size() > 0) {
            const [price, shop, movie, version] = this.rented.peek();
            const key = `${shop},${movie}`;
            if (this.rentedKeys.has(key) && this.versions.get(key) === version) {
                break;
            }
            this.rented.pop();
        }
        if (this.rented.size() === 0) {
            break;
        }
        selected.push(this.rented.pop());
    }

    for (const entry of selected) {
        this.rented.push(entry);
    }
    return selected.map((entry) => [entry[1], entry[2]]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

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