Medium

题目描述

给定餐厅数组 restaurants，其中 restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]。你需要使用三个过滤器来过滤餐厅。

veganFriendly 过滤器可以是 true（意味着你只需要包含 veganFriendlyi 为 true 的餐厅）或 false（意味着你可以包含任何餐厅）。此外，你还有 maxPrice 和 maxDistance 过滤器，分别是你应该考虑的餐厅价格和距离的最大值。

返回过滤后的餐厅 ID 数组，按评分从高到低排序。对于评分相同的餐厅，按 id 从高到低排序。为简单起见，当 veganFriendlyi 和 veganFriendly 为 true 时取值为 1，为 false 时取值为 0。

示例 1：

输入：restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 1, maxPrice = 50, maxDistance = 10
输出：[3,1,5]
解释：
餐厅信息如下：
餐厅 1 [id=1, rating=4, veganFriendly=1, price=40, distance=10]
餐厅 2 [id=2, rating=8, veganFriendly=0, price=50, distance=5]
餐厅 3 [id=3, rating=8, veganFriendly=1, price=30, distance=4]
餐厅 4 [id=4, rating=10, veganFriendly=0, price=10, distance=3]
餐厅 5 [id=5, rating=1, veganFriendly=1, price=15, distance=1]
过滤 veganFriendly = 1, maxPrice = 50, maxDistance = 10 后，我们有餐厅 3、餐厅 1 和餐厅 5（按评分从高到低排序）。

示例 2：

输入：restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 50, maxDistance = 10
输出：[4,3,2,1,5]

示例 3：

输入：restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 30, maxDistance = 3
输出：[4,5]

约束条件：

  • 1 <= restaurants.length <= 10^4
  • restaurants[i].length == 5
  • 1 <= idi, ratingi, pricei, distancei <= 10^5
  • 1 <= maxPrice, maxDistance <= 10^5
  • veganFriendlyi 和 veganFriendly 为 0 或 1
  • 所有 idi 都不相同

解题思路

这道题的解题思路很直观，分为两个步骤：过滤 和 排序。

首先进行过滤操作：我们需要根据三个条件筛选餐厅：

  1. 素食友好性：如果 veganFriendly = 1，只保留 veganFriendlyi = 1 的餐厅；如果 veganFriendly = 0，则所有餐厅都满足条件
  2. 价格限制：餐厅价格不能超过 maxPrice
  3. 距离限制：餐厅距离不能超过 maxDistance

然后进行排序操作：按照题目要求的排序规则对筛选后的餐厅进行排序：

  1. 首先按评分从高到低排序
  2. 评分相同时，按 ID 从高到低排序

实现上，我们可以遍历所有餐厅，将满足条件的餐厅添加到结果数组中，然后使用自定义比较器进行排序。比较器的逻辑是：如果评分不同就按评分降序，如果评分相同就按 ID 降序。

时间复杂度主要来自排序操作，空间复杂度主要是存储过滤后的餐厅数据。

代码实现

class Solution {
public:
    vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        vector<vector<int>> filtered;
        
        // 过滤餐厅
        for (auto& restaurant : restaurants) {
            int id = restaurant[0];
            int rating = restaurant[1];
            int vegan = restaurant[2];
            int price = restaurant[3];
            int distance = restaurant[4];
            
            // 检查是否满足所有过滤条件
            if ((veganFriendly == 0 || vegan == 1) && 
                price <= maxPrice && 
                distance <= maxDistance) {
                filtered.push_back(restaurant);
            }
        }
        
        // 排序：首先按评分降序，然后按ID降序
        sort(filtered.begin(), filtered.end(), [](const vector<int>& a, const vector<int>& b) {
            if (a[1] != b[1]) {
                return a[1] > b[1];  // 评分降序
            }
            return a[0] > b[0];  // ID降序
        });
        
        // 提取ID
        vector<int> result;
        for (auto& restaurant : filtered) {
            result.push_back(restaurant[0]);
        }
        
        return result;
    }
};

class Solution:
    def filterRestaurants(self, restaurants: List[List[int]], veganFriendly: int, maxPrice: int, maxDistance: int) -> List[int]:
        # 过滤餐厅
        filtered = []
        for restaurant in restaurants:
            id, rating, vegan, price, distance = restaurant
            
            # 检查是否满足所有过滤条件
            if (veganFriendly == 0 or vegan == 1) and price <= maxPrice and distance <= maxDistance:
                filtered.append(restaurant)
        
        # 排序：首先按评分降序，然后按ID降序
        filtered.sort(key=lambda x: (-x[1], -x[0]))
        
        # 提取ID
        return [restaurant[0] for restaurant in filtered]

public class Solution {
    public IList<int> FilterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        var filtered = new List<int[]>();
        
        // 过滤餐厅
        foreach (var restaurant in restaurants) {
            int id = restaurant[0];
            int rating = restaurant[1];
            int vegan = restaurant[2];
            int price = restaurant[3];
            int distance = restaurant[4];
            
            // 检查是否满足所有过滤条件
            if ((veganFriendly == 0 || vegan == 1) && 
                price <= maxPrice && 
                distance <= maxDistance) {
                filtered.Add(restaurant);
            }
        }
        
        // 排序：首先按评分降序，然后按ID降序
        filtered.Sort((a, b) => {
            if (a[1] != b[1]) {
                return b[1].CompareTo(a[1]);  // 评分降序
            }
            return b[0].CompareTo(a[0]);  // ID降序
        });
        
        // 提取ID
        var result = new List<int>();
        foreach (var restaurant in filtered) {
            result.Add(restaurant[0]);
        }
        
        return result;
    }
}

var filterRestaurants = function(restaurants, veganFriendly, maxPrice, maxDistance) {
    return restaurants
        .filter(restaurant => {
            const [id, rating, vegan, price, distance] = restaurant;
            return (veganFriendly === 0 || vegan === 1) && 
                   price <= maxPrice && 
                   distance <= maxDistance;
        })
        .sort((a, b) => {
            if (a[1] !== b[1]) {
                return b[1] - a[1];
            }
            return b[0] - a[0];
        })
        .map(restaurant => restaurant[0]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)其中 n 是餐厅数量，过滤操作是 O(n)，排序操作是 O(n log n)
空间复杂度O(n)需要额外空间存储过滤后的餐厅数据和结果数组