LeetCode2353.设计食物评分系统题解

一、题目描述

本题要求设计一个食物评分系统，该系统需要支持以下两种操作：

修改系统中列出的某种食物的评分：可以对系统中已有的某种食物的评分进行更新。返回系统中某一类烹饪方式下评分最高的食物：如果存在评分相同的情况，需要返回字典序较小的食物名称。 类定义及方法

实现 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 ""; // 如果堆为空，返回空字符串（理论上不会发生） } };

通过以上实现，我们可以高效地完成食物评分系统的设计，满足题目要求的两种操作。