LeetCode 题解工作台
餐厅过滤器
给你一个餐馆信息数组 restaurants ，其中 restaurants[i] = [id i , rating i , veganFriendly i , price i , distance i ] 。你必须使用以下三个过滤器来过滤这些餐馆信息。 其中素食者友好过滤器 veganFriend…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·排序
答案摘要
我们先将数组 `restaurants` 按照 `rating` 和 `id` 两个维度进行排序，然后再按照题目给定的条件进行筛选即可。 时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 是数组 `restaurants` 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·排序 题型思路
题目描述
给你一个餐馆信息数组 restaurants，其中 restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]。你必须使用以下三个过滤器来过滤这些餐馆信息。
其中素食者友好过滤器 veganFriendly 的值可以为 true 或者 false，如果为 true 就意味着你应该只包括 veganFriendlyi 为 true 的餐馆，为 false 则意味着可以包括任何餐馆。此外，我们还有最大价格 maxPrice 和最大距离 maxDistance 两个过滤器，它们分别考虑餐厅的价格因素和距离因素的最大值。
过滤后返回餐馆的 id，按照 rating 从高到低排序。如果 rating 相同，那么按 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] 解释：餐馆与示例 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^4restaurants[i].length == 51 <= idi, ratingi, pricei, distancei <= 10^51 <= maxPrice, maxDistance <= 10^5veganFriendlyi和veganFriendly的值为 0 或 1 。- 所有
idi各不相同。
解题思路
方法一：排序
我们先将数组 restaurants 按照 rating 和 id 两个维度进行排序，然后再按照题目给定的条件进行筛选即可。
时间复杂度 ，空间复杂度 。其中 是数组 restaurants 的长度。
class Solution:
def filterRestaurants(
self,
restaurants: List[List[int]],
veganFriendly: int,
maxPrice: int,
maxDistance: int,
) -> List[int]:
restaurants.sort(key=lambda x: (-x[1], -x[0]))
ans = []
for idx, _, vegan, price, dist in restaurants:
if vegan >= veganFriendly and price <= maxPrice and dist <= maxDistance:
ans.append(idx)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate is expected to understand how to filter an array based on multiple criteria.
- question_mark
The sorting of the filtered array should be done using custom sorting with multiple conditions.
- question_mark
The candidate should explain how they would handle edge cases, such as no restaurants meeting the criteria.
常见陷阱
外企场景- error
Failing to correctly apply the vegan-friendly filter, resulting in incorrect results for restaurants with 0 or 1 values.
- error
Not handling the sorting correctly, such as failing to break ties based on the restaurant ID in case of equal ratings.
- error
Not considering edge cases where no restaurants pass the filter, which should return an empty list.
进阶变体
外企场景- arrow_right_alt
Consider different variations where only one of the filters (vegan-friendly, maxPrice, or maxDistance) is applied.
- arrow_right_alt
Handle cases where multiple restaurants have identical ratings and IDs, ensuring the correct sorting and filtering behavior.
- arrow_right_alt
Modify the problem to return the full restaurant details (instead of just IDs) after filtering and sorting.