花花酱 LeetCode 2353. Design a Food Rating System

Hashtable + TreeSet / OrderedSet

用了三个Hashtable…

每个菜系用一个TreeSet来保存从高到低的菜色排名，查询的时候只要拿出第一个就好了。

修改的时候，拿出迭代器，删除原来的评分，再把新的评分加入（别忘了更新迭代器）

时间复杂度：构造O(nlogn)，修改O(logn)，查询O(1)

空间复杂度：O(n)

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);

请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website
您可以通过在亚马逊上购物（任意商品）来支持我们

Paypal

Venmo
huahualeetcode

微信打赏

Be First to Comment