1333. 餐厅过滤器

1333. 餐厅过滤器

难度: 中等

来源: 每日一题 2023.09.27

给你一个餐馆信息数组 restaurants，其中 restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]。你必须使用以下三个过滤器来过滤这些餐馆信息。

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

过滤后返回餐馆的 id，按照 rating 从高到低排序。如果 rating 相同，那么按 id 从高到低排序。简单起见， $veganFriendl{y}_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 <= $i{d}_i$, $ratin{g}_i$, $pric{e}_i$, $distanc{e}_i$ <= $10^5$
• 1 <= maxPrice, maxDistance <= $10^5$
• $veganFriendl{y}_i$ 和 $veganFriendly$ 的值为 0 或 1 。
• 所有 $i{d}_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 的长度成线性相关关系.

  结果如下所示.