LeetCode 2353. 设计食物评分系统题解
一、题目描述
本题要求设计一个食物评分系统，该系统需要支持以下两种操作：
- 修改系统中列出的某种食物的评分：可以对系统中已有的某种食物的评分进行更新。
- 返回系统中某一类烹饪方式下评分最高的食物：如果存在评分相同的情况，需要返回字典序较小的食物名称。
类定义及方法
实现 FoodRatings 类，包含以下方法：
- 构造函数
FoodRatings(String[] foods, String[] cuisines, int[] ratings)：用于初始化系统，foods数组存储食物名称，cuisines数组存储对应食物的烹饪方式，ratings数组存储对应食物的初始评分，三个数组长度均为n。 void changeRating(String food, int newRating)：修改名字为food的食物的评分。String highestRated(String cuisine)：返回指定烹饪方式cuisine下评分最高的食物的名字。如果存在并列，返回字典序较小的名字。
示例
输入：
["FoodRatings", "highestRated", "highestRated", "changeRating", "highestRated", "changeRating", "highestRated"]
[[["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], [9, 12, 8, 15, 14, 7]], ["korean"], ["japanese"], ["sushi", 16], ["japanese"], ["ramen", 16], ["japanese"]]输出：
[null, "kimchi", "ramen", null, "sushi", null, "ramen"]解释：
- 初始化
FoodRatings类，包含多种食物及其烹饪方式和评分。 - 调用
highestRated("korean")返回 "kimchi"，因为它是韩式料理中评分最高的。 - 调用
highestRated("japanese")返回 "ramen"，因为它是日式料理中评分最高的。 - 调用
changeRating("sushi", 16)将 "sushi" 的评分更新为 16。 - 再次调用
highestRated("japanese")返回 "sushi"，因为更新后它是日式料理中评分最高的。 - 调用
changeRating("ramen", 16)将 "ramen" 的评分更新为 16。 - 最后调用
highestRated("japanese")返回 "ramen"，因为 "sushi" 和 "ramen" 评分相同，但 "ramen" 的字典序更小。
提示
- 数组长度
n的范围是1 <= n <= 2 * 10^4。 - 食物名称和烹饪方式字符串长度范围是
1 <= foods[i].length, cuisines[i].length <= 10，且由小写英文字母组成。 - 评分范围是
1 <= ratings[i] <= 10^8。 foods中的所有字符串互不相同。- 在
changeRating调用中，food是系统中已有的食物名称；在highestRated调用中，cuisine是系统中至少一种食物的烹饪方式。 - 最多调用
changeRating和highestRated总计2 * 10^4次。
二、解决思路
为了实现这个食物评分系统，我们可以使用两个哈希表来存储数据：
cuisineHeap：这是一个unordered_map，键为烹饪方式cuisine，值为一个最大堆（优先队列）。每个最大堆存储对应烹饪方式下的所有食物及其评分，堆的排序规则是先按评分从大到小排序，如果评分相同则按食物名称的字典序从小到大排序。foodInfo：这也是一个unordered_map，键为食物名称food，值为一个pair，包含该食物的烹饪方式和当前评分。
自定义比较函数
为了实现最大堆的排序规则，我们需要自定义一个比较函数 ComparePair：
struct ComparePair {
bool operator()(const pair<string, int>& a, const pair<string, int>& b) const {
if (a.second != b.second) {
return a.second < b.second; // 按第二个元素从大到小排序
}
return a.first > b.first; // 如果第二个元素相等，按第一个元素字典序从小到大排序
}
};这个比较函数确保了堆顶元素是评分最高且字典序最小的食物。
具体实现步骤
1. 构造函数 FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings)
遍历输入的三个数组，将每个食物及其评分插入到对应烹饪方式的最大堆中，并记录该食物的烹饪方式和评分到 foodInfo 中。
FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
int n = foods.size();
for (int i = 0; i < n; i++) {
string food = foods[i];
string cuisine = cuisines[i];
int rating = ratings[i];
// 将 (food, rating) 插入对应 cuisine 的最大堆
cuisineHeap[cuisine].emplace(food, rating);
// 记录 food 对应的 cuisine 和 rating
foodInfo[food] = {cuisine, rating};
}
}2. void changeRating(string food, int newRating)
首先从 foodInfo 中获取该食物的烹饪方式，然后更新该食物的评分。接着将新的 (food, newRating) 插入到对应烹饪方式的最大堆中。
void changeRating(string food, int newRating) {
// 更新 foodInfo 中 food 的 rating
string cuisine = foodInfo[food].first;
foodInfo[food].second = newRating;
// 将新的 (food, newRating) 插入对应 cuisine 的最大堆
cuisineHeap[cuisine].emplace(food, newRating);
}3. string highestRated(string cuisine)
找到对应烹饪方式的最大堆，由于堆中可能存在已经被更新过的无效元素（即堆顶元素的评分与 foodInfo 中记录的评分不一致），我们需要跳过这些无效元素，直到找到有效的最高评分的食物。
string highestRated(string cuisine) {
// 找到对应 cuisine 的最大堆
auto& heap = cuisineHeap[cuisine];
// 跳过堆顶已经被更新的无效元素
while (!heap.empty()) {
string topFood = heap.top().first;
int topRating = heap.top().second;
// 检查堆顶元素是否是最新的 rating
if (foodInfo[topFood].second == topRating) {
return topFood; // 返回有效的最高评分的 food
}
// 如果堆顶元素无效，移除它
heap.pop();
}
return ""; // 如果堆为空，返回空字符串（理论上不会发生）
}三、复杂度分析
- 时间复杂度：
- 构造函数的时间复杂度为 $O(n log n)$，其中 $n$ 是食物的数量。因为每次插入堆的操作时间复杂度为 $O(log n)$，总共需要插入 $n$ 个元素。
changeRating方法的时间复杂度为 $O(log n)$，主要是插入堆的操作。highestRated方法的时间复杂度最坏情况下为 $O(n log n)$，因为可能需要移除堆中所有无效元素，但平均情况下为 $O(log n)$。
- 空间复杂度：
- 主要的空间开销是两个哈希表，空间复杂度为 $O(n)$，其中 $n$ 是食物的数量。
四、完整代码
#include <unordered_map>
#include <queue>
#include <vector>
#include <string>
using namespace std;
// 自定义比较函数
struct ComparePair {
bool operator()(const pair<string, int>& a, const pair<string, int>& b) const {
if (a.second != b.second) {
return a.second < b.second; // 按第二个元素从大到小排序
}
return a.first > b.first; // 如果第二个元素相等，按第一个元素字典序从小到大排序
}
};
class FoodRatings {
private:
// 哈希表1：存储每个 cuisine 对应的最大堆
unordered_map<string, priority_queue<pair<string, int>, vector<pair<string, int>>, ComparePair>> cuisineHeap;
// 哈希表2：存储每个 food 对应的 cuisine 和 rating
unordered_map<string, pair<string, int>> foodInfo;
public:
FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
int n = foods.size();
for (int i = 0; i < n; i++) {
string food = foods[i];
string cuisine = cuisines[i];
int rating = ratings[i];
// 将 (food, rating) 插入对应 cuisine 的最大堆
cuisineHeap[cuisine].emplace(food, rating);
// 记录 food 对应的 cuisine 和 rating
foodInfo[food] = {cuisine, rating};
}
}
void changeRating(string food, int newRating) {
// 更新 foodInfo 中 food 的 rating
string cuisine = foodInfo[food].first;
foodInfo[food].second = newRating;
// 将新的 (food, newRating) 插入对应 cuisine 的最大堆
cuisineHeap[cuisine].emplace(food, newRating);
}
string highestRated(string cuisine) {
// 找到对应 cuisine 的最大堆
auto& heap = cuisineHeap[cuisine];
// 跳过堆顶已经被更新的无效元素
while (!heap.empty()) {
string topFood = heap.top().first;
int topRating = heap.top().second;
// 检查堆顶元素是否是最新的 rating
if (foodInfo[topFood].second == topRating) {
return topFood; // 返回有效的最高评分的 food
}
// 如果堆顶元素无效，移除它
heap.pop();
}
return ""; // 如果堆为空，返回空字符串（理论上不会发生）
}
};通过以上实现，我们可以高效地完成食物评分系统的设计，满足题目要求的两种操作。