餐厅过滤器

1333. 餐厅过滤器

给你一个餐馆信息数组 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 各不相同。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) { } };

rust 解法, 执行用时: 8 ms, 内存消耗: 3.2 MB, 提交时间: 2023-09-27 07:40:09

impl Solution {
    pub fn filter_restaurants(
        restaurants: Vec<Vec<i32>>,
        vegan_friendly: i32,
        max_price: i32,
        max_distance: i32,
    ) -> Vec<i32> {
        let mut restaurants = restaurants
            .iter()
            .filter(|r| r[2] >= vegan_friendly && r[3] <= max_price && r[4] <= max_distance)
            .collect::<Vec<_>>();
        restaurants.sort_unstable_by_key(|r| (-r[1], -r[0]));

        restaurants.iter().map(|r| r[0]).collect()
    }
}

cpp 解法, 执行用时: 72 ms, 内存消耗: 28.3 MB, 提交时间: 2023-09-27 07:39:35

class Solution {
public:
    vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        int n = restaurants.size();
        vector<vector<int>> filtered;
        for (int i = 0; i < n; i++) {
            if (restaurants[i][3] <= maxPrice && restaurants[i][4] <= maxDistance && !(veganFriendly && !restaurants[i][2])) {
                filtered.push_back(restaurants[i]);
            }
        }
        sort(filtered.begin(), filtered.end(), [](vector<int> &v1, vector<int> &v2) -> bool {
            return v1[1] > v2[1] || (v1[1] == v2[1] && v1[0] > v2[0]);
        });
        vector<int> res;
        for (auto &v : filtered) {
            res.push_back(v[0]);
        }
        return res;
    }
};

golang 解法, 执行用时: 48 ms, 内存消耗: 7 MB, 提交时间: 2023-09-27 07:39:05

func filterRestaurants(restaurants [][]int, veganFriendly int, maxPrice int, maxDistance int) []int {
    filtered := [][]int{}
    for _, r := range restaurants {
        if r[3] <= maxPrice && r[4] <= maxDistance && !(veganFriendly == 1 && r[2] == 0) {
            filtered = append(filtered, r)
        }
    }
    sort.Slice(filtered, func(i, j int) bool {
        return filtered[i][1] > filtered[j][1] || (filtered[i][1] == filtered[j][1] && filtered[i][0] > filtered[j][0])
    })
    res := []int{}
    for _, r := range filtered {
        res = append(res, r[0])
    }
    return res
}

javascript 解法, 执行用时: 76 ms, 内存消耗: 46.2 MB, 提交时间: 2022-12-09 12:37:11

/**
 * @param {number[][]} restaurants
 * @param {number} veganFriendly
 * @param {number} maxPrice
 * @param {number} maxDistance
 * @return {number[]}
 */
const filterRestaurants = (restaurants, veganFriendly, maxPrice, maxDistance) => {
  const filtered = [];
  for (const item of restaurants) {
    (veganFriendly === 0 || item[2] === veganFriendly)
    && item[3] <= maxPrice
    && item[4] <= maxDistance
    && filtered.push(item);
  }
  filtered.sort((a, b) => a[1] === b[1] ? b[0] - a[0] : b[1] - a[1]);
  const ret = new Uint32Array(filtered.length);
  for (let i = 0; i < filtered.length; ++i) {
    ret[i] = filtered[i][0];
  }
  return ret;
};

python3 解法, 执行用时: 76 ms, 内存消耗: 20.4 MB, 提交时间: 2022-12-09 12:36:01

class Solution:
    def filterRestaurants(self, restaurants: List[List[int]], veganFriendly: int, maxPrice: int, maxDistance: int) -> List[int]:
        for rest in restaurants:
            if veganFriendly and not rest[2]:
                rest[1]=0
            elif maxPrice<rest[3] or maxDistance<rest[4]:
                rest[1]=0
        restaurants.sort(key=lambda x:[x[1],x[0]],reverse=True)
        return [r[0] for r in restaurants if r[1]]

java 解法, 执行用时: 9 ms, 内存消耗: 50.2 MB, 提交时间: 2022-12-09 12:34:17

class Solution {
  public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice,
      int maxDistance) {
    return Arrays.stream(restaurants)
        .filter(
            x -> (veganFriendly == 1 ? x[2] == 1 : true) && x[3] <= maxPrice && x[4] <= maxDistance)
        .sorted(new Comparator<int[]>() {
          @Override
          public int compare(int[] i1, int[] i2) {
            return i1[1] == i2[1] ? i2[0] - i1[0] : i2[1] - i1[1];
          }
        }).mapToInt(x -> x[0]).boxed().collect(Collectors.toList());
  }
}

python3 解法, 执行用时: 48 ms, 内存消耗: 20.7 MB, 提交时间: 2022-12-09 12:33:41

class Solution:
    def filterRestaurants(self, restaurants: List[List[int]], veganFriendly: int, maxPrice: int, maxDistance: int) -> List[int]:
        ans = []
        for id, rating, veganFriend, price, distance in restaurants:
            if price <= maxPrice and distance <= maxDistance:
                if veganFriend == veganFriendly or not veganFriendly:
                    ans.append([rating, id])
        ans.sort(reverse=True)
        return [item[1] for item in ans]

上一题

下一题

详情