1333. 餐厅过滤器
难度: 中等
来源: 每日一题 2023.09.27
给你一个餐馆信息数组 restaurants
,其中 restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]
。你必须使用以下三个过滤器来过滤这些餐馆信息。
其中素食者友好过滤器 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$ 各不相同。
class Solution {
public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
}
}
分析与题解
-
模拟法 + 双条件排序
这个题目看似题目很长很难解的样子, 实际上当读懂题意之后非常简单, 主要是分为两大部分, 一个是搜索出条件合适的餐厅, 另外就是对这些餐厅进行排序.
-
筛选出合适条件的餐厅, 筛选条件包括
veganFriendly
、maxPrice
以及maxDistance
.for(int i = 0; i < restaurants.length; i++) { if(veganFriendly == 1 && restaurants[i][2] == 0) { continue; } if(restaurants[i][3] <= maxPrice && restaurants[i][4] <= maxDistance) { filter.add(restaurants[i]); } }
-
根据 rating 以及 id 对筛选的餐厅进行排序.
filter.sort(new Comparator<int[]>() {//使用List接口的方法排序 @Override public int compare(int[] o1, int[] o2) { Integer rating1 = o1[1]; Integer rating2 = o2[1]; if (rating2.compareTo(rating1) != 0) { return rating2.compareTo(rating1); } else { Integer rating3 = o1[0]; Integer rating4 = o2[0]; return rating4.compareTo(rating3); } } });
-
组装结果数组.
for(int[] item : filter) { result.add(item[0]); } return result;
接下来我们一起看一下整体的解题思路, 代码如下所示.
class Solution { public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) { List<Integer> result = new ArrayList<>(); List<int[]> filter = new ArrayList<>(); for(int i = 0; i < restaurants.length; i++) { if(veganFriendly == 1 && restaurants[i][2] == 0) { continue; } if(restaurants[i][3] <= maxPrice && restaurants[i][4] <= maxDistance) { filter.add(restaurants[i]); } } filter.sort(new Comparator<int[]>() {//使用List接口的方法排序 @Override public int compare(int[] o1, int[] o2) { Integer rating1 = o1[1]; Integer rating2 = o2[1]; if (rating2.compareTo(rating1) != 0) { return rating2.compareTo(rating1); } else { Integer rating3 = o1[0]; Integer rating4 = o2[0]; return rating4.compareTo(rating3); } } }); for(int[] item : filter) { result.add(item[0]); } return result; } }
复杂度分析:
- 时间复杂度: O(2n), 一遍筛选遍历, 一遍组装遍历, 所以时间复杂度是
O(2n)
- 空间复杂度: O(2n), 两个数组, 每一个数组最大存储元素量与
restaurants
的长度成线性相关关系.
结果如下所示.
-
Comments | 0 条评论