[M数据结构]lc2353.设计食物评分系统(数据结构+set平衡树+懒删除堆)

文章目录 1. 题目来源2. 题目解析

1. 题目来源

链接：2353. 设计食物评分系统

题单：

待补充 2. 题目解析

这种 平衡树、优先队列的，暂时拿 go 还写不了，没有合适的板子用。就先拿 C++ 写吧，日后看看啥时候会补齐这个板子。

---

方法一：set 平衡树写法

涉及到一些 set 的基本操作和技巧操作。set 是一颗平衡树，底层是 红黑树。从小到大排序。常用技巧，set 平衡树输入的时候取负值，然后 begin() 位置就是实际的最大值。

---

方法二：懒删除堆

一个很妙的技巧，之前好像没啥印象，也是记录这个题的目的。chang 的时候，直接往堆中插记录。查询的时候，直接取堆顶，如果堆顶的评分和哈希表一致的话，那就说明这个就是有效元素，否则这个元素无效，直接 pop 即可。最终，堆顶即为有效数据。

---

时间复杂度： O ( n log ⁡ n ) O(n \log n) O(nlogn)空间复杂度： O ( n ) O(n) O(n)

---

C++ STL::set 写法：

class FoodRatings { public: unordered_map<string, pair<string, int>> m1; // 【食物，<烹饪方式， 得分>】 unordered_map<string, set<pair<int, string>>> m2; // 【烹饪方式，set<得分，名称>】 FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) { int n = foods.size(); for (int i = 0; i < n; i ++ ) { m1[foods[i]] = {cuisines[i], ratings[i]}; // 常用技巧，set 平衡树输入的时候取负值，然后 begin() 位置就是实际的最大值 m2[cuisines[i]].insert({-ratings[i], foods[i]}); } } void changeRating(string food, int newRating) { auto f = m1[food]; m1[food] = {f.first, newRating}; m2[f.first].erase({-f.second, food}); m2[f.first].insert({-newRating, food}); } string highestRated(string cuisine) { return m2[cuisine].begin()->second; } }; /** * Your FoodRatings object will be instantiated and called as such: * FoodRatings* obj = new FoodRatings(foods, cuisines, ratings); * obj->changeRating(food,newRating); * string param_2 = obj->highestRated(cuisine); */

---

懒删除，小顶堆。写法

class FoodRatings { public: unordered_map<string, pair<string, int>> m1; // 懒删除堆。注意，这里需要用小顶堆。因为需要按照字典序进行排序输出。 unordered_map<string, priority_queue<pair<int, string>, vector<pair<int, string>>, greater<>>> m2; FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) { int n = foods.size(); for (int i = 0; i < n; i ++ ) { m1[foods[i]] = {cuisines[i], ratings[i]}; m2[cuisines[i]].push({-ratings[i], foods[i]}); } } void changeRating(string food, int newRating) { auto &f = m1[food]; m1[food] = {f.first, newRating}; // 堆中直接插入即可 m2[f.first].push({-newRating, food}); } string highestRated(string cuisine) { // 这里需要引用...否则 TTL auto &m = m2[cuisine]; // 懒删除堆经典操作：查看堆顶元素值是否和实际值一致，不一致则 pop，一致则说明找到了最值 while (m.size() && -m1[m.top().second].second != m.top().first) { m.pop(); } return m.top().second; } }; /** * Your FoodRatings object will be instantiated and called as such: * FoodRatings* obj = new FoodRatings(foods, cuisines, ratings); * obj->changeRating(food,newRating); * string param_2 = obj->highestRated(cuisine); */