Hashtable + TreeSet / OrderedSet
用了三个Hashtable…
- 菜名 -> 菜系
- 菜系 -> Treemap
- 菜名 -> 所在Treemap中的迭代器
每个菜系用一个TreeSet来保存从高到低的菜色排名，查询的时候只要拿出第一个就好了。
修改的时候，拿出迭代器，删除原来的评分，再把新的评分加入（别忘了更新迭代器）
时间复杂度：构造O(nlogn)，修改O(logn)，查询O(1)
空间复杂度：O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
class FoodRatings { public: FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) { const int n = foods.size(); for (int i = 0; i < n; ++i) { n_[foods[i]] = cuisines[i]; m_[foods[i]] = c_[cuisines[i]].emplace(-ratings[i], foods[i]).first; } } void changeRating(string food, int newRating) { const string& cuisine = n_[food]; c_[cuisine].erase(m_[food]); m_[food] = c_[cuisine].emplace(-newRating, food).first; } string highestRated(string cuisine) { return begin(c_[cuisine])->second; } private: unordered_map<string, set<pair<int, string>>> c_; // cuisine -> {{-rating, name}} unordered_map<string, string> n_; // food -> cuisine unordered_map<string, set<pair<int, string>>::iterator> m_; // food -> set iterator }; /** * 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); */ |