MediumRating 1782

2353. Design a Food Rating System

arrayhash-tablestringdesignheap-priority-queueordered-set

解題說明

Design a Food Rating System

題目描述：設計一個食物評分系統。初始化時給定食物列表、對應的烹飪方式和評分。支援兩個操作：changeRating(food, newRating) 修改指定食物的評分；highestRated(cuisine) 返回指定烹飪方式中評分最高的食物名稱（評分相同時返回字典序最小的）。

解題思路：使用三個資料結構：

foodRating：食物 → 當前評分
foodCuisine：食物 → 烹飪方式
cuisineFoods：烹飪方式 → set<pair<int, string>> 有序集合

set 中存放 (-rating, food_name)，這樣 begin() 就能得到評分最高且字典序最小的食物。changeRating 時先刪除舊的 pair，再插入新的 pair。

C++ 解法

複雜度分析

時間複雜度：初始化 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) 返回評分最低的食物，資料結構需要如何修改？
如果要支援刪除食物的操作，如何處理？
如果 highestRated 需要返回前 k 名食物列表，如何高效實現？

Design a Food Rating System — CaffeCode