力扣2353题解析：如何设计高效的食物评分系统？从数据结构选择到实现技巧
一、问题分析
需要支持两种操作：修改评分和查询最高评分食物
查询需要考虑评分和字典序双重条件
数据规模要求高效实现（10^5次操作）
二、数据结构选择
使用unordered_map存储食物基本信息（O(1)访问）
使用set存储每种烹饪方式下的食物（自动排序）
巧妙利用pair和负评分实现降序排列
三、关键实现细节
四、完整代码
class FoodRatings {
private:
// 食物到烹饪方式和评分的映射
unordered_map<string, pair<string, int>> foodInfo;
// 烹饪方式到(评分,食物)的有序集合
unordered_map<string, set<pair<int, string>>> cuisineMap;
public:
FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
for(int i = 0; i < foods.size(); ++i) {
string food = foods[i];
string cuisine = cuisines[i];
int rating = ratings[i];
// 存储食物信息
foodInfo[food] = {cuisine, rating};
// 将食物按评分和名称添加到对应烹饪方式的集合
cuisineMap[cuisine].insert({-rating, food}); // 使用负评分实现降序
}
}
void changeRating(string food, int newRating) {
auto& info = foodInfo[food];
string cuisine = info.first;
int oldRating = info.second;
// 从原烹饪方式集合中移除旧记录
cuisineMap[cuisine].erase({-oldRating, food});
// 更新食物评分
info.second = newRating;
// 添加新记录到集合
cuisineMap[cuisine].insert({-newRating, food});
}
string highestRated(string cuisine) {
// 返回集合中第一个元素的食物名（评分最高且字典序最小）
return cuisineMap[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);
*/五、常见错误
忘记处理同名食物
修改评分时未更新两个数据结构
忽略字典序比较规则
原创内容 转载请注明出处
