上次编辑到这里，代码来自缓存 点击恢复默认模板
class MovieRentingSystem {
public:
MovieRentingSystem(int n, vector<vector<int>>& entries) {
}
vector<int> search(int movie) {
}
void rent(int shop, int movie) {
}
void drop(int shop, int movie) {
}
vector<vector<int>> report() {
}
};
/**
* Your MovieRentingSystem object will be instantiated and called as such:
* MovieRentingSystem* obj = new MovieRentingSystem(n, entries);
* vector<int> param_1 = obj->search(movie);
* obj->rent(shop,movie);
* obj->drop(shop,movie);
* vector<vector<int>> param_4 = obj->report();
*/
golang 解法, 执行用时: 816 ms, 内存消耗: 77.9 MB, 提交时间: 2023-09-23 11:33:31
type MovieRentingSystem struct {
M map[string]*Node //根据 “shop + movie”找到节点，修改节点状态
H H //全局有序集合，用于输出全局已借出电影的top5。使用小根堆。
MovieRanked map[int][]*Node //每个电影一个有序集合，由于节点个数不会变（只有“是否借出”状态会变）。直接用有序数组即可（继续用小根堆也行），查找时过滤掉已借出的
}
func Constructor(n int, entries [][]int) MovieRentingSystem {
m := make(map[string]*Node, 0)
h := H{}
rank := make(map[int][]*Node, 0)
for _, v := range entries {
node := &Node{
Shop: v[0],
Movie: v[1],
Price: v[2],
IsRent: false,
}
key := fmt.Sprintf("%v_%v", v[0], v[1])
m[key] = node
rank[v[1]] = append(rank[v[1]], node)
}
for _, v := range rank {
sort.Slice(v, func(i, j int) bool {
if v[i].Price < v[j].Price {
return true
}
if v[i].Price > v[j].Price {
return false
}
return v[i].Shop < v[j].Shop
})
}
return MovieRentingSystem{m, h, rank}
}
func (this *MovieRentingSystem) Search(movie int) []int {
ret := make([]int, 0)
h := this.MovieRanked[movie]
for _, x := range h {
if x.IsRent {
continue
}
ret = append(ret, x.Shop)
if len(ret) >= 5 {
break
}
}
return ret
}
func (this *MovieRentingSystem) Rent(shop int, movie int) {
key := fmt.Sprintf("%v_%v", shop, movie)
node := this.M[key]
node.IsRent = true
heap.Push(&this.H, node) //可能重复入堆，后续出堆要去重
}
func (this *MovieRentingSystem) Drop(shop int, movie int) {
key := fmt.Sprintf("%v_%v", shop, movie)
node := this.M[key]
node.IsRent = false
}
func (this *MovieRentingSystem) Report() [][]int {
ret := make([][]int, 0)
tmp := make([]*Node, 0)
m := make(map[*Node]bool, 0)
for len(this.H) > 0 {
x := heap.Pop(&this.H).(*Node)
if x.IsRent == false {
continue
}
if m[x] == true {
continue
}
m[x] = true
tmp = append(tmp, x)
ret = append(ret, []int{x.Shop, x.Movie})
if len(ret) >= 5 {
break
}
}
for i := 0; i < len(tmp); i++ {
heap.Push(&this.H, tmp[i])
}
return ret
}
type Node struct {
Shop int
Movie int
Price int
IsRent bool // true 表示已借出
}
type H []*Node
func (h H) Len() int { return len(h) }
func (h H) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h H) Less(i, j int) bool {
if h[i].Price < h[j].Price {
return true
}
if h[i].Price > h[j].Price {
return false
}
if h[i].Shop < h[j].Shop {
return true
}
if h[i].Shop > h[j].Shop {
return false
}
return h[i].Movie < h[j].Movie
}
func (h *H) Push(v interface{}) { *h = append(*h, v.(*Node)) }
func (h *H) Pop() interface{} { n := len(*h); x := (*h)[n-1]; (*h) = (*h)[0 : n-1]; return x }
/**
* Your MovieRentingSystem object will be instantiated and called as such:
* obj := Constructor(n, entries);
* param_1 := obj.Search(movie);
* obj.Rent(shop,movie);
* obj.Drop(shop,movie);
* param_4 := obj.Report();
*/
java 解法, 执行用时: 581 ms, 内存消耗: 249.4 MB, 提交时间: 2023-09-23 11:30:26
class MovieRentingSystem {
private Map<Integer, Map<Integer, int[]>> shopMap;
private TreeSet<int[]> out;
private TreeSet<int[]> has;
public MovieRentingSystem(int n, int[][] entries) {
shopMap = new HashMap<>();
for (int i = 0; i < n; i++) {
shopMap.put(i, new HashMap<>());
}
out = new TreeSet<>((a, b) -> {
if (a[2] != b[2]) {
return a[2] - b[2];
} else if (a[0] != b[0]) {
return a[0] - b[0];
} else {
return a[1] - b[1];
}
});
has = new TreeSet<>((a, b) -> {
if (a[1] != b[1]) {
return a[1] - b[1];
} else if (a[2] != b[2]) {
return a[2] - b[2];
} else {
return a[0] - b[0];
}
});
for (int[] entry : entries) {
shopMap.get(entry[0]).put(entry[1], entry);
has.add(entry);
}
}
public List<Integer> search(int movie) {
List<Integer> list = new ArrayList<>(5);
//找出5个最便宜的 如果价格相同就商店id排序
int[] find = new int[]{-1, movie, -1};
for (int i = 0; i < 5; i++) {
int[] next = has.ceiling(find);
if (next != null && next[1] == movie) {
list.add(next[0]);
} else {
break;
}
find[0] = next[0] + 1;
find[2] = next[2];
}
return list;
}
public void rent(int shop, int movie) {
int[] get = shopMap.get(shop).get(movie);
has.remove(get);
out.add(get);
}
public void drop(int shop, int movie) {
int[] put = shopMap.get(shop).get(movie);
has.add(put);
out.remove(put);
}
public List<List<Integer>> report() {
List<List<Integer>> list = new ArrayList<>(5);
//找出5个最便宜的 如果价格相同就商店id排序
int[] find = new int[]{-1, -1, -1};
for (int i = 0; i < 5; i++) {
int[] next = out.ceiling(find);
if (next != null) {
List<Integer> list2 = new ArrayList<>(2);
list2.add(next[0]);
list2.add(next[1]);
list.add(list2);
} else {
break;
}
find[0] = next[0];
find[1] = next[1]+1;
find[2] = next[2];
}
return list;
}
}
/**
* Your MovieRentingSystem object will be instantiated and called as such:
* MovieRentingSystem obj = new MovieRentingSystem(n, entries);
* List<Integer> param_1 = obj.search(movie);
* obj.rent(shop,movie);
* obj.drop(shop,movie);
* List<List<Integer>> param_4 = obj.report();
*/
cpp 解法, 执行用时: 1360 ms, 内存消耗: 405.1 MB, 提交时间: 2023-09-23 11:29:32
class MovieRentingSystem {
public:
set<pair<int, int>> mv[100001];
set<pair<int, pair<int, int>>> rt;
map<pair<int, int>, int> prc;
MovieRentingSystem(int n, vector<vector<int>>& entries) {
for (size_t i = 0; i < entries.size(); i++) {
int x=entries[i][0], y=entries[i][1], z=entries[i][2];
prc[make_pair(x, y)] = z;
mv[y].insert(make_pair(z, x));
}
}
vector<int> search(int movie) {
auto it = mv[movie].begin(); vector<int> v;
for (size_t i=0; i<5 && it!=mv[movie].end(); i++,it++) v.push_back(it -> second);
return v;
}
void rent(int shop, int movie) {
int price = prc[make_pair(shop, movie)];
mv[movie].erase(make_pair(price, shop));
rt.insert(make_pair(price, make_pair(shop, movie)));
}
void drop(int shop, int movie) {
int price = prc[make_pair(shop, movie)];
mv[movie].insert(make_pair(price, shop));
rt.erase(make_pair(price, make_pair(shop, movie)));
}
vector<vector<int>> report() {
auto it = rt.begin(); vector<vector<int>> v;
for (size_t i=0; i<5 && it!=rt.end(); i++,it++) v.push_back({(it->second).first, (it->second).second});
return v;
}
};
/**
* Your MovieRentingSystem object will be instantiated and called as such:
* MovieRentingSystem* obj = new MovieRentingSystem(n, entries);
* vector<int> param_1 = obj->search(movie);
* obj->rent(shop,movie);
* obj->drop(shop,movie);
* vector<vector<int>> param_4 = obj->report();
*/
cpp 解法, 执行用时: 1148 ms, 内存消耗: 386.4 MB, 提交时间: 2023-09-23 11:28:56
class MovieRentingSystem {
private:
// 需要自行实现 pair<int, int> 的哈希函数
static constexpr auto pairHash = [fn = hash<int>()](const pair<int, int>& o) {return (fn(o.first) << 16) ^ fn(o.second);};
unordered_map<pair<int, int>, int, decltype(pairHash)> t_price{0, pairHash};
unordered_map<int, set<pair<int, int>>> t_valid;
set<tuple<int, int, int>> t_rent;
public:
MovieRentingSystem(int n, vector<vector<int>>& entries) {
for (const auto& entry: entries) {
t_price[{entry[0], entry[1]}] = entry[2];
t_valid[entry[1]].emplace(entry[2], entry[0]);
}
}
vector<int> search(int movie) {
if (!t_valid.count(movie)) {
return {};
}
vector<int> ret;
auto it = t_valid[movie].begin();
for (int i = 0; i < 5 && it != t_valid[movie].end(); ++i, ++it) {
ret.push_back(it->second);
}
return ret;
}
void rent(int shop, int movie) {
int price = t_price[{shop, movie}];
t_valid[movie].erase({price, shop});
t_rent.emplace(price, shop, movie);
}
void drop(int shop, int movie) {
int price = t_price[{shop, movie}];
t_valid[movie].emplace(price, shop);
t_rent.erase({price, shop, movie});
}
vector<vector<int>> report() {
vector<vector<int>> ret;
auto it = t_rent.begin();
for (int i = 0; i < 5 && it != t_rent.end(); ++i, ++it) {
ret.emplace_back(initializer_list<int>{get<1>(*it), get<2>(*it)});
}
return ret;
}
};
/**
* Your MovieRentingSystem object will be instantiated and called as such:
* MovieRentingSystem* obj = new MovieRentingSystem(n, entries);
* vector<int> param_1 = obj->search(movie);
* obj->rent(shop,movie);
* obj->drop(shop,movie);
* vector<vector<int>> param_4 = obj->report();
*/
python3 解法, 执行用时: 1256 ms, 内存消耗: 102.4 MB, 提交时间: 2023-09-23 11:28:12
import sortedcontainers
class MovieRentingSystem:
def __init__(self, n: int, entries: List[List[int]]):
self.t_price = dict()
self.t_valid = defaultdict(sortedcontainers.SortedList)
self.t_rent = sortedcontainers.SortedList()
for shop, movie, price in entries:
self.t_price[(shop, movie)] = price
self.t_valid[movie].add((price, shop))
def search(self, movie: int) -> List[int]:
t_valid_ = self.t_valid
if movie not in t_valid_:
return []
return [shop for (price, shop) in t_valid_[movie][:5]]
def rent(self, shop: int, movie: int) -> None:
price = self.t_price[(shop, movie)]
self.t_valid[movie].discard((price, shop))
self.t_rent.add((price, shop, movie))
def drop(self, shop: int, movie: int) -> None:
price = self.t_price[(shop, movie)]
self.t_valid[movie].add((price, shop))
self.t_rent.discard((price, shop, movie))
def report(self) -> List[List[int]]:
return [(shop, movie) for price, shop, movie in self.t_rent[:5]]
# 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()