題目描述:
設計一個食物評分系統。初始化時給定食物列表、對應的烹飪方式和評分。支援兩個操作:changeRating(food, newRating) 修改指定食物的評分;highestRated(cuisine) 返回指定烹飪方式中評分最高的食物名稱(評分相同時返回字典序最小的)。
解題思路: 使用三個資料結構:
foodRating:食物 → 當前評分foodCuisine:食物 → 烹飪方式cuisineFoods:烹飪方式 → set<pair<int, string>> 有序集合set 中存放 (-rating, food_name),這樣 begin() 就能得到評分最高且字典序最小的食物。changeRating 時先刪除舊的 pair,再插入新的 pair。
時間複雜度:初始化 O(n log n);changeRating O(log n)(set 的刪除和插入);highestRated O(1)
空間複雜度:O(n) — 儲存所有食物的映射和有序集合
1. Initialize three maps: - foodRating: food -> rating - foodCuisine: food -> cuisine - cuisineFoods: cuisine -> sorted set of (-rating, food_name) 2. changeRating(food, newRating): a. Remove (-oldRating, food) from cuisine's set b. Insert (-newRating, food) into cuisine's set c. Update foodRating[food] 3. highestRated(cuisine): a. Return the food name from the first element of cuisine's set
Lazy Heap 法:使用 priority_queue 儲存 (-rating, food)。changeRating 時不刪除舊元素,而是在 highestRated 時檢查堆頂元素的評分是否與 foodRating 一致,不一致則彈出(延遲刪除)。插入 O(log n),查詢攤銷 O(log n)。
有序映射(std::map)法:用 map<pair<int,string>, ...> 取代 set,本質相同但如果需要範圍查詢可擴展性更好。
lowestRated(cuisine) 返回評分最低的食物,資料結構需要如何修改?