LC.P1333[餐厅过滤器]

方法一：排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        List<Integer> ans = new ArrayList<>();
        List<int[]> list = new ArrayList<>();
        for (int[] r : restaurants) {
            if (veganFriendly == 1 && r[2] == 0) continue;
            if (r[3] > maxPrice) continue;
            if (r[4] > maxDistance) continue;
            list.add(r);
        }
        list.sort((a, b) -> {
            if (a[1] != b[1]) return b[1] - a[1];
            else return b[0] - a[0];
        });
        for (int[] a : list) {
            ans.add(a[0]);
        }
        return ans;
    }
}
  • 时间复杂度：$O(nlogn)$
  • 空间复杂度：$O(n)$

方法二：stream流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        return Arrays.stream(restaurants)
                .filter(r -> veganFriendly == 0 || r[2] == veganFriendly)
                .filter(r -> r[3] <= maxPrice)
                .filter(r -> r[4] <= maxDistance)
                .sorted((a, b) -> {
                    if (a[1] != b[1]) return b[1] - a[1];
                    else return b[0] - a[0];
                })
                .map(r -> r[0])
                .collect(Collectors.toList());
    }
}
  • 时间复杂度：$O(nlogn)$
  • 空间复杂度：$O(n)$