餐厅过滤器

难度: Medium

给你一个餐馆信息数组 restaurants，其中 restaurants[i] = [id_i, rating_i, veganFriendly_i, price_i, distance_i]。你必须使用以下三个过滤器来过滤这些餐馆信息。

其中素食者友好过滤器 veganFriendly 的值可以为 true 或者 false，如果为 true 就意味着你应该只包括 veganFriendly_i 为 true 的餐馆，为 false 则意味着可以包括任何餐馆。此外，我们还有最大价格 maxPrice 和最大距离 maxDistance 两个过滤器，它们分别考虑餐厅的价格因素和距离因素的最大值。

过滤后返回餐馆的 id，按照 rating 从高到低排序。如果 rating 相同，那么按 id 从高到低排序。简单起见， veganFriendly_i 和 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]
解释：餐馆与示例 1 相同，但在 veganFriendly = 0 的过滤条件下，应该考虑所有餐馆。

示例 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 <= id_i, rating_i, price_i, distance_i<= 10^5
1 <= maxPrice, maxDistance <= 10^5
veganFriendly_i 和 veganFriendly 的值为 0 或 1 。
所有 id_i 各不相同。

Submission

运行时间: 36 ms

内存: 23.2 MB

from typing import List

class Solution:
    def filterRestaurants(self, restaurants: List[List[int]], veganFriendly: int, maxPrice: int, maxDistance: int) -> List[int]:
        # 根据过滤条件筛选餐馆
        filtered_restaurants = []
        for restaurant in restaurants:
            id, rating, vegan, price, distance = restaurant
            if (veganFriendly == 1 and vegan == 1) or veganFriendly == 0:
                if price <= maxPrice and distance <= maxDistance:
                    filtered_restaurants.append([id, rating])
        
        # 按评分从高到低排序，如果评分相同则按id从高到低排序
        filtered_restaurants.sort(key=lambda x: (-x[1], -x[0]))
        
        # 提取排序后的餐馆id列表
        result = [restaurant[0] for restaurant in filtered_restaurants]
        
        return result

solution = Solution()

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
print(solution.filterRestaurants(restaurants, veganFriendly, maxPrice, maxDistance))  # 输出: [3, 1, 5]

veganFriendly = 0
maxPrice = 50
maxDistance = 10
print(solution.filterRestaurants(restaurants, veganFriendly, maxPrice, maxDistance))  # 输出: [4, 3, 2, 1, 5]

veganFriendly = 0
maxPrice = 30
maxDistance = 3
print(solution.filterRestaurants(restaurants, veganFriendly, maxPrice, maxDistance))  # 输出: [4, 5]

Explain

首先，题解的方法是通过遍历餐馆列表来筛选出符合条件的餐馆。具体的筛选条件包括：如果veganFriendly为1，则只选择vegan为1的餐馆；同时，餐馆的价格不超过maxPrice，且餐馆的距离不超过maxDistance。将符合条件的餐馆按评分降序排序，如果评分相同，则按ID降序排序。最后，从排序后的列表中提取餐馆ID，形成结果列表返回。

时间复杂度: O(n log n)

空间复杂度: O(m)

from typing import List

class Solution:
    def filterRestaurants(self, restaurants: List[List[int]], veganFriendly: int, maxPrice: int, maxDistance: int) -> List[int]:
        # 根据过滤条件筛选餐馆
        filtered_restaurants = []
        for restaurant in restaurants:
            id, rating, vegan, price, distance = restaurant
            # 检查veganFriendly条件和vegan状态
            if (veganFriendly == 1 and vegan == 1) or veganFriendly == 0:
                # 检查价格和距离条件
                if price <= maxPrice and distance <= maxDistance:
                    filtered_restaurants.append([id, rating])
        
        # 排序：先按评分降序，评分相同则按id降序
        filtered_restaurants.sort(key=lambda x: (-x[1], -x[0]))
        
        # 获取排序后的餐馆id列表
        result = [restaurant[0] for restaurant in filtered_restaurants]
        
        return result

solution = Solution()

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
print(solution.filterRestaurants(restaurants, veganFriendly, maxPrice, maxDistance))  # 输出: [3, 1, 5]

veganFriendly = 0
maxPrice = 50
maxDistance = 10
print(solution.filterRestaurants(restaurants, veganFriendly, maxPrice, maxDistance))  # 输出: [4, 3, 2, 1, 5]

veganFriendly = 0
maxPrice = 30
maxDistance = 3
print(solution.filterRestaurants(restaurants, veganFriendly, maxPrice, maxDistance))  # 输出: [4, 5]

Explore

这个逻辑是基于`veganFriendly`参数的定义。当`veganFriendly`为1时，表示用户只想看到提供纯素食选项的餐厅。因此，如果餐厅的`vegan`标识为0（即餐厅不提供纯素食选项），这家餐厅就不符合用户的要求，应被排除在外。这是为了确保过滤后的结果准确反映用户的餐饮偏好。

在使用排序函数时，通过指定先根据`rating`降序排序，如果`rating`相同，则根据`id`降序排序。这种排序方式确保了即使多个餐馆的评分和ID完全相同，它们的相对顺序依然可以通过ID来确定。然而，在Python中，使用`sort()`方法进行的排序是稳定的，意味着相同键值的元素将保持原有顺序。但由于我们在这里明确使用了`id`作为第二排序条件，实际上已经不会有相同评分和ID的情况出现，因此结果的稳定性已经通过排序逻辑得到了保证。

在这个特定的情况中，使用列表来存储过滤后的餐馆信息是因为我们需要保持元素的顺序，以便可以按照评分和ID进行排序。字典或集合虽然在某些情况下提供了更快的查找速度，但它们不保留元素的插入顺序（Python 3.7+的字典除外）。此外，我们需要的操作主要是遍历和排序，列表在这方面提供了直接和高效的支持。

在极端情况下，如果`maxPrice`或`maxDistance`为0，那么任何价格大于0或距离大于0的餐馆都应该被排除在外。这是根据最大价格和最大距离的过滤条件直接决定的。如果这两个参数中任何一个为0，过滤逻辑将自动排除所有不符合此极限条件的餐馆。这确保了过滤器能够正确处理所有边界情况，符合条件的餐馆（如果有的话）将被正确返回。