力扣(LeetCode)1333. 餐厅过滤器(C++)

优先队列

请读者读题，应该会发现两个重点：过滤器和排序。大家有没有发现这个效果，有点像xx点评: 大家选店一般在口味/距离/价格能接受的前提下，选评分最高的那家店hh，这就是过滤器的效果。排序是说，对满足心理预期的店子，按 rating 从高到低排序，店子的rating 相同时，按照 id 从高到低排序。

算法流程：

• 维护优先队列(大根堆)，存放 {rating, id} !!
• 正序遍历 restaurant ，设置过滤器(条件语句)跳过不符合要求的店子，如果店子符合要求，则向优先队列存入当前店子的 {rating, id}
• 遍历结束，优先队列存放店子的顺序就是答案:

过滤器筛选过的店子，按 rating 从高到低排序，店子的rating 相同时，按照 id 从高到低排序。

class Solution {
public:
    vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        priority_queue<pair<int, int>> pq;
        for (vector<int> &restaurant : restaurants) {
            int id = restaurant[0], rating = restaurant[1], veganF = restaurant[2], price = restaurant[3];
            int distance = restaurant[4];
            if (veganFriendly){
                if (!veganF) continue;
            }
            if (price > maxPrice || distance > maxDistance) continue;
            pq.push({rating, id});
        }
        vector<int> ans;
        while (pq.size()) {
            ans.push_back(pq.top().second);
            pq.pop();
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度 $O(nlogn)$ : $n$ 是餐厅数量($restaurants.size()$)，遍历 $restaurant$ 同时维护优先队列的时间复杂度 $O(nlogn)$
空间复杂度 $O(n)$ : 优先队列 $pq$ 的最坏空间复杂度 $O(n)$

AC

致语

• 理解思路很重要
• 读者有问题请留言，清墨看到就会回复的。