引航博景网站做的很好吗,淄博 网站建设,网站建设前期分析,服务网站建设公司来源#xff1a;力扣#xff08;LeetCode#xff09;
描述#xff1a;
给你一个餐馆信息数组 restaurants#xff0c;其中 restaurants[i] [idi, ratingi, veganFriendlyi, pricei, distancei]。你必须使用以下三个过滤器来过滤这些餐馆信息。
其中素食者友好过滤器 v…来源力扣LeetCode
描述
给你一个餐馆信息数组 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 [id1, rating4, veganFriendly1, price40, distance10]
餐馆 2 [id2, rating8, veganFriendly0, price50, distance5]
餐馆 3 [id3, rating8, veganFriendly1, price30, distance4]
餐馆 4 [id4, rating10, veganFriendly0, price10, distance3]
餐馆 5 [id5, rating1, veganFriendly1, price15, distance1]
在按照 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 104restaurants[i].length 51 idi, ratingi, pricei, distancei 1051 maxPrice, maxDistance 105veganFriendlyi 和 veganFriendly 的值为 0 或 1 。所有 idi 各不相同。
方法排序
按照题目要求我们首先获取数组 restaurants 经过三个过滤器后的 filtered 数组。遍历 restaurants假设当前遍历的元素为 restaurants[i]如果以下条件都满足
restaurants[i][3] maxPricerestaurants[i][4] maxDistanceveganFriendly 为 false 或 restaurants[i][2] 为 true
那么将 restaurants[i] 加入到 filtered 中。然后将 filtered 按照 rating 从高到低排序如果 rating 相同则按 id 从高到低排序。最后返回 filtered 的所有 id 作为结果。
代码
class Solution {
public:vectorint filterRestaurants(vectorvectorint restaurants, int veganFriendly, int maxPrice, int maxDistance) {int n restaurants.size();vectorvectorint 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(), [](vectorint v1, vectorint v2) - bool {return v1[1] v2[1] || (v1[1] v2[1] v1[0] v2[0]);});vectorint res;for (auto v : filtered) {res.push_back(v[0]);}return res;}
};时间 72ms 击败 86.81%使用 C 的用户 内存 27.50MB 击败 28.57%使用 C 的用户 复杂度分析 时间复杂度O(nlogn)其中 n 是数组 restaurants 的长度。排序需要 O(nlogn)。空间复杂度O(n)。保存 filtered 需要 O(n) 的空间。 author力扣官方题解
