1912. Design Movie Rental System
题目简介
这是一道困难题，而且是比较有意思的系统设计题
题目要求我们设计一个电影租赁系统，题目要求我们实现以下方法：
MovieRentingSystem(int n, int[][] entries)：构造函数，参数 n 代表我们有 n 家店、参数 entries 代表 [shop, movie, price] 三元组，表示在 shop 中有 movie 可以租借，价格为 moneyList<Integer> search(int movie)：搜索所有有 movie 且还未出租的店家，找到 price 最低的前 5 家店返回，如果 price 一样，则 shop 低的优先返回void rent(int shop, int movie)：将 movie 从 shop 中租出去void drop(int shop, int movie)：把 movie 还到 shop（只能还回原 shop）List<List<Integer>> report()：从所有租出去的电影中，返回最便宜的前五个电影的 [shop, movie] 二元组，如果 price 一致，返回 shop 低的，如果 shop 也一致，返回 movie 低的
解题思路
这题的思路有两个：
- 排序数组
- 小顶堆
前者在数据量大的情况下性能表现不如后者，但是在 leetcode 的测试 case 中性能会比后者好一些，我直接放代码，不赘述，后面主要讲解小顶堆的思路
这道题的关键在于 search 与 report 方法，要想办法减少这两个方法的复杂度
search 方法我们可以用一个 movie => heap 的 movieHeap 来保存从 map 到小顶堆的映射，此处的 heap 只需要保存 [shop, price] 就好；除了 map 之外，我们还需要一个 Set unRentedMovie 来保存还未出租的 movie，用来筛选 map 返回
report 方法我们可以直接维护一个小顶堆 rentedHeap 来保存所有已经出租出去的电影，这个 heap 我们保存 [shop, movie, price]
最后在 rent 的时候，题目给的参数没有给 price，所以我们还需要一个 map priceMap 来保存从 [shop, movie] 到 price 的映射
Javascript（小顶堆）
/**
* @param {number} n
* @param {number[][]} entries
*/
var MovieRentingSystem = function (n, entries) {
this.resultLimit = 5
// movie => Heap([shop, price]) for search
this.movieHeap = new Map()
// shop#movie
this.unRentedMovie = new Set()
// Heap([shop, movie, price]) for report
this.rentedHeap = new MyHeap(([sA, mA, pA], [sB, mB, pB]) => {
return pA - pB || sA - sB || mA - mB
})
// shop#movie => price
this.priceMap = new Map()
for (const [shop, movie, price] of entries) {
const key = getKey(shop, movie)
this.unRentedMovie.add(key)
this.priceMap.set(key, price)
if (!this.movieHeap.has(movie)) {
this.movieHeap.set(movie, new MyHeap(([sA, pA], [sB, pB]) => {
return pA - pB || sA - sB
}))
}
this.movieHeap.get(movie).push([shop, price])
}
};
/**
* @param {number} movie
* @return {number[]}
*/
MovieRentingSystem.prototype.search = function (movie) {
if (!this.movieHeap.has(movie)) {
return []
}
const res = []
const retain = []
const heap = this.movieHeap.get(movie)
const seen = new Set()
while (!heap.isEmpty() && res.length < this.resultLimit) {
const [shop, price] = heap.pop()
const key = getKey(shop, movie)
// only pick unrented movie
if (this.unRentedMovie.has(key) && !seen.has(key)) {
res.push(shop)
// only keep unrented movie to prevent worse case(keep searching rented movie)
retain.push([shop, price])
seen.add(key)
}
}
// push all back to the heap
retain.forEach(item => heap.push(item))
return res
};
/**
* @param {number} shop
* @param {number} movie
* @return {void}
*/
MovieRentingSystem.prototype.rent = function (shop, movie) {
const key = getKey(shop, movie)
if (this.unRentedMovie.has(key)) {
this.unRentedMovie.delete(key)
}
// test case ensure to have shop and movie in shop's unrent list
const price = this.priceMap.get(key)
this.rentedHeap.push([shop, movie, price])
};
/**
* @param {number} shop
* @param {number} movie
* @return {void}
*/
MovieRentingSystem.prototype.drop = function (shop, movie) {
const key = getKey(shop, movie)
this.unRentedMovie.add(key)
if (!this.movieHeap.has(movie)) {
this.movieHeap.set(movie, new MyHeap(([sA, pA], [sB, pB]) => {
return pA - pB || sA - sB
}))
}
const price = this.priceMap.get(key)
this.movieHeap.get(movie).push([shop, price])
// we will adjust the rentedHeap later
};
/**
* @return {number[][]}
*/
MovieRentingSystem.prototype.report = function () {
const res = []
const retain = []
// prevent duplicate data
const seen = new Set()
while (!this.rentedHeap.isEmpty() && res.length < this.resultLimit) {
const [shop, movie, price] = this.rentedHeap.pop()
const key = getKey(shop, movie)
// only keep rented movie
if (!this.unRentedMovie.has(key) && !seen.has(key)) {
res.push([shop, movie])
retain.push([shop, movie, price])
seen.add(key)
}
}
retain.forEach(item => this.rentedHeap.push(item))
return res
};
const getKey = (shop, movie) => {
return `${shop}#${movie}`
}
class MyHeap {
constructor(compare) {
this.heap = []
this.compare = compare
}
peek() {
return this.heap[0]
}
isEmpty() {
return this.heap.length === 0
}
push(item) {
this.heap.push(item)
this.heapifyUp(this.heap.length - 1)
}
pop() {
if (this.heap.length <= 1) {
return this.heap.pop()
}
const res = this.heap[0]
this.heap[0] = this.heap.pop()
this.heapifyDown(0)
return res
}
heapifyUp(index) {
let parent = (index - 1) >> 1
if (parent >= 0 && this.compare(this.heap[index], this.heap[parent]) < 0) {
// let temp = this.heap[index]
// this.heap[index] = this.heap[parent]
// this.heap[parent] = temp
[this.heap[index], this.heap[parent]] = [this.heap[parent], this.heap[index]]
this.heapifyUp(parent)
}
}
heapifyDown(index) {
const left = index * 2 + 1
const right = index * 2 + 2
let competitive = index
if (left < this.heap.length && this.compare(this.heap[left], this.heap[competitive]) < 0) {
competitive = left
}
if (right < this.heap.length && this.compare(this.heap[right], this.heap[competitive]) < 0) {
competitive = right
}
if (competitive !== index) {
[this.heap[competitive], this.heap[index]] = [this.heap[index], this.heap[competitive]]
this.heapifyDown(competitive)
}
}
}
Javascript（排序数组）
/**
* @param {number} n
* @param {number[][]} entries
*/
var MovieRentingSystem = function (_n, entries) {
this.maxNumSearchResults = 5;
let sorted = [...entries]
.sort(([shop1, _1, price1], [shop2, _2, price2]) => {
let priceDiff = price1 - price2;
return priceDiff? priceDiff: shop1 - shop2;
});
//{ movie: [ [shop1, priceLowest] ... [shopN, priceHighest] ] }
this.movies = sorted
.reduce((movies, [shop, movie]) => {
let shops = movies[movie];
if(shops == undefined)
shops = movies[movie] = [];
shops.push(shop);
return movies;
}, {});
/*
{
shop: { movie: { price } }
}
*/
this.shops = sorted
.reduce((shops, [shop, movie, price]) => {
let data = shops[shop];
if(data == undefined)
data = shops[shop] = {};
data[movie] = {price};
return shops;
}, {});
//i = [shop, movie]
this.rented = [];
};
/**
* @param {number} movie
* @return {number[]}
*/
MovieRentingSystem.prototype.search = function (movie) {
let results = [],
shops = this.movies[movie];
if (shops) {
for (let i = 0, l = shops.length; results.length < this.maxNumSearchResults && i < l; i++) {
let shop = shops[i];
if (!this.shops[shop][movie].rented) results.push(shop);
}
}
return results;
};
/**
* @param {number} shop
* @param {number} movie
* @return {void}
*/
MovieRentingSystem.prototype.rent = function (shop, movie) {
if (this.shops[shop][movie].rented == undefined) {
let rentData = [shop, movie];
this.shops[shop][movie].rented = rentData;
this.rented.push(rentData);
}
};
/**
* @param {number} shop
* @param {number} movie
* @return {void}
*/
MovieRentingSystem.prototype.drop = function (shop, movie) {
let movieData = this.shops[shop]?.[movie].rented;
if (movieData) {
this.rented.splice(this.rented.indexOf(movieData), 1);
delete this.shops[shop][movie].rented;
}
};
/**
* @return {number[][]}
*/
MovieRentingSystem.prototype.report = function () {
return this.rented
.sort(([shop1, movie1], [shop2, movie2]) => {
let priceDiff = this.shops[shop1][movie1].price - this.shops[shop2][movie2].price;
if(!priceDiff)
return shop1 == shop2? movie1 - movie2 : shop1 - shop2;
return priceDiff;
})
.slice(0, this.maxNumSearchResults);
};
/**
* Your MovieRentingSystem object will be instantiated and called as such:
* var obj = new MovieRentingSystem(n, entries)
* var param_1 = obj.search(movie)
* obj.rent(shop,movie)
* obj.drop(shop,movie)
* var param_4 = obj.report()
*/