Medium

题目描述

设计一个食物评分系统，可以执行以下操作：

  • 修改系统中已列出食物的评分
  • 返回系统中某种菜系评分最高的食物

实现 FoodRatings 类：

  • FoodRatings(String[] foods, String[] cuisines, int[] ratings) 初始化系统。食物由 foods、cuisines 和 ratings 描述，它们的长度都为 n。
    • foods[i] 是第 i 种食物的名称
    • cuisines[i] 是第 i 种食物的菜系类型
    • ratings[i] 是第 i 种食物的初始评分
  • void changeRating(String food, int newRating) 修改名称为 food 的食物的评分
  • String highestRated(String cuisine) 返回指定菜系类型中评分最高的食物名称。如果存在并列，返回字典序较小的名称

注意，如果字符串 x 在字典序上小于字符串 y，那么 x 在字典中排在 y 之前，也就是说，要么 x 是 y 的前缀，要么在第一个不同的位置 i 处，x[i] 在字母表中排在 y[i] 之前。

示例 1：

输入
["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 foodRatings = new FoodRatings(["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], [9, 12, 8, 15, 14, 7]);
foodRatings.highestRated("korean"); // 返回 "kimchi"
                                    // "kimchi" 是评分最高的韩式食物，评分为 9
foodRatings.highestRated("japanese"); // 返回 "ramen"
                                      // "ramen" 是评分最高的日式食物，评分为 14
foodRatings.changeRating("sushi", 16); // "sushi" 现在的评分为 16
foodRatings.highestRated("japanese"); // 返回 "sushi"
                                      // "sushi" 是评分最高的日式食物，评分为 16
foodRatings.changeRating("ramen", 16); // "ramen" 现在的评分为 16
foodRatings.highestRated("japanese"); // 返回 "ramen"
                                      // "sushi" 和 "ramen" 的评分都是 16
                                      // 但是，"ramen" 在字典序上小于 "sushi"

提示：

  • 1 <= n <= 2 * 10^4
  • n == foods.length == cuisines.length == ratings.length
  • 1 <= foods[i].length, cuisines[i].length <= 10
  • foods[i]、cuisines[i] 由小写英文字母组成
  • 1 <= ratings[i] <= 10^8
  • foods 中的所有字符串互不相同
  • 在对 changeRating 的所有调用中，food 都是系统中食物的名称
  • 在对 highestRated 的所有调用中，cuisine 在系统中至少有一种食物
  • 最多调用 changeRating 和 highestRated 总计 2 * 10^4 次

解题思路

这道题需要设计一个高效的数据结构来支持两个主要操作：修改食物评分和查询某菜系最高评分的食物。

核心思路：

  1. 使用哈希表存储食物到菜系和评分的映射关系
  2. 为每个菜系维护一个有序集合（优先队列），按评分降序和字典序升序排列
  3. 修改评分时需要更新相关数据结构

具体实现：

  • foodToCuisine: 映射食物名到菜系类型
  • foodToRating: 映射食物名到当前评分
  • cuisineToFoods: 映射菜系到该菜系下所有食物的有序集合

有序集合的排序规则：

  • 首先按评分降序排列（评分高的在前）
  • 评分相同时按食物名字典序升序排列

changeRating操作：

  1. 从原有序集合中删除旧的(评分, 食物名)对
  2. 更新食物评分
  3. 将新的(评分, 食物名)对插入有序集合

highestRated操作： 直接返回对应菜系有序集合的第一个元素（评分最高且字典序最小）

这种设计确保了所有操作都有较好的时间复杂度，适合频繁的查询和更新操作。

代码实现

class FoodRatings {
private:
    unordered_map<string, string> foodToCuisine;
    unordered_map<string, int> foodToRating;
    unordered_map<string, set<pair<int, string>>> cuisineToFoods;
    
public:
    FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
        for (int i = 0; i < foods.size(); i++) {
            foodToCuisine[foods[i]] = cuisines[i];
            foodToRating[foods[i]] = ratings[i];
            cuisineToFoods[cuisines[i]].insert({-ratings[i], foods[i]});
        }
    }
    
    void changeRating(string food, int newRating) {
        string cuisine = foodToCuisine[food];
        int oldRating = foodToRating[food];
        
        cuisineToFoods[cuisine].erase({-oldRating, food});
        cuisineToFoods[cuisine].insert({-newRating, food});
        foodToRating[food] = newRating;
    }
    
    string highestRated(string cuisine) {
        return cuisineToFoods[cuisine].begin()->second;
    }
};

from sortedcontainers import SortedSet

class FoodRatings:

    def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
        self.food_to_cuisine = {}
        self.food_to_rating = {}
        self.cuisine_to_foods = {}
        
        for i in range(len(foods)):
            self.food_to_cuisine[foods[i]] = cuisines[i]
            self.food_to_rating[foods[i]] = ratings[i]
            
            if cuisines[i] not in self.cuisine_to_foods:
                self.cuisine_to_foods[cuisines[i]] = SortedSet()
            
            self.cuisine_to_foods[cuisines[i]].add((-ratings[i], foods[i]))

    def changeRating(self, food: str, newRating: int) -> None:
        cuisine = self.food_to_cuisine[food]
        old_rating = self.food_to_rating[food]
        
        self.cuisine_to_foods[cuisine].remove((-old_rating, food))
        self.cuisine_to_foods[cuisine].add((-newRating, food))
        self.food_to_rating[food] = newRating

    def highestRated(self, cuisine: str) -> str:
        return self.cuisine_to_foods[cuisine][0][1]

public class FoodRatings {
    private Dictionary<string, string> foodToCuisine;
    private Dictionary<string, int> foodToRating;
    private Dictionary<string, SortedSet<(int rating, string food)>> cuisineToFoods;

    public FoodRatings(string[] foods, string[] cuisines, int[] ratings) {
        foodToCuisine = new Dictionary<string, string>();
        foodToRating = new Dictionary<string, int>();
        cuisineToFoods = new Dictionary<string, SortedSet<(int, string)>>();
        
        for (int i = 0; i < foods.Length; i++) {
            foodToCuisine[foods[i]] = cuisines[i];
            foodToRating[foods[i]] = ratings[i];
            
            if (!cuisineToFoods.ContainsKey(cuisines[i])) {
                cuisineToFoods[cuisines[i]] = new SortedSet<(int, string)>(
                    Comparer<(int rating, string food)>.Create((a, b) => {
                        if (a.rating != b.rating) return b.rating.CompareTo(a.rating);
                        return a.food.CompareTo(b.food);
                    })
                );
            }
            
            cuisineToFoods[cuisines[i]].Add((ratings[i], foods[i]));
        }
    }
    
    public void ChangeRating(string food, int newRating) {
        string cuisine = foodToCuisine[food];
        int oldRating = foodToRating[food];
        
        cuisineToFoods[cuisine].Remove((oldRating, food));
        cuisineToFoods[cuisine].Add((newRating, food));
        foodToRating[food] = newRating;
    }
    
    public string HighestRated(string cuisine) {
        return cuisineToFoods[cuisine].Min.food;
    }
}

var FoodRatings = function(foods, cuisines, ratings) {
    this.foodToCuisine = new Map();
    this.foodToRating = new Map();
    this.cuisineToFoods = new Map();
    
    for (let i = 0; i < foods.length; i++) {
        this.foodToCuisine.set(foods[i], cuisines[i]);
        this.foodToRating.set(foods[i], ratings[i]);
        
        if (!this.cuisineToFoods.has(cuisines[i])) {
            this.cuisineToFoods.set(cuisines[i], []);
        }
        
        this.cuisineToFoods.get(cuisines[i]).push([ratings[i], foods[i]]);
    }
    
    // Sort each cuisine's food list
    for (let [cuisine, foodList] of this.cuisineToFoods) {
        foodList.sort((a, b) => {
            if (a[0] !== b[0]) return b[0] - a[0]; // Higher rating first
            return a[1].localeCompare(b[1]); // Lexicographically smaller name first
        });
    }
};

FoodRatings.prototype.changeRating = function(food, newRating) {
    const cuisine = this.foodToCuisine.get(food);
    const oldRating = this.foodToRating.get(food);
    
    const foodList = this.cuisineToFoods.get(cuisine);
    
    // Remove old entry
    for (let i = 0; i < foodList.length; i++) {
        if (foodList[i][0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
初始化O(n log n)O(n)
changeRatingO(log n)O(1)
highestRatedO(1)O(1)

其中 n 是食物的总数。初始化时需要将所有食物插入到对应的有序集合中；changeRating 需要删除和插入操作，都是 O(log n)；highestRated 直接返回有序集合的第一个元素，是 O(1)。空间复杂度主要用于存储哈希表和有序集合。

相关题目