preface

Nuggets in the recent brush topic activities, also come to join in the excitement. The problem was brushed out at random

Topic describes

Because copying text format is not good, I directly map, can also see directlyThe original

Difficulty: Medium

The sample

Example 1

Input: ,4,1,40,10 restaurants = [[1], [2,8,0,50,5], [3,8,1,30,4],,10,0,10,3 [4], [5,1,1,15,1]], veganFriendly = 1, maxPrice = 50, MaxDistance = 10 output: [3,1,5] explanation: these restaurants are: 5 [id=1, rating= 80, price=50, distance= 50] 5 [id=2, rating= 80, price=50, distance= 50] Distance =5 [id= 5, rating= 80, price= 50, distance=5, price= 50, distance=5, rating= 80, Price =5, distance= 5 [id=5, rating=1, price=15, distance=1] After filtering with maxPrice = 50 and maxDistance = 10, we get restaurant 3, restaurant 1, and restaurant 5 (ranked from highest to lowest).Copy the code

Example 2

Input: ,4,1,40,10 restaurants = [[1], [2,8,0,50,5], [3,8,1,30,4],,10,0,10,3 [4], [5,1,1,15,1]], veganFriendly = 0, maxPrice = 50, MaxDistance = 10 output: [4,3,2,1,5] explanation: restaurants are the same as example 1, but with veganFriendly = 0 filtering, all restaurants should be considered.Copy the code

Example 3

Input: ,4,1,40,10 restaurants = [[1], [2,8,0,50,5], [3,8,1,30,4],,10,0,10,3 [4], [5,1,1,15,1]], veganFriendly = 0, maxPrice = 30, MaxDistance = 3Copy the code

Tip:

Their thinking

First of all, select the restaurants that meet the requirements:

  • Whether the current diner is vegetarian or not, the restaurant can only be vegetarian
  • The distance must not exceed the acceptable distance
  • The price must not exceed the acceptable price

This is usually order n

        for (int[] restaurant : restaurants) {
            if ((veganFriendly == 1 && restaurant[2] != 1) || restaurant[3] > maxPrice || restaurant[4] > maxDistance) {
                continue;
            }
        }
Copy the code

Secondly, the restaurants screened need to be sorted. Sorting is not recommended during screening, otherwise it will cause a lot of repeated operations. Here I chose to use quicksort for the final sort, order nlogn.

AC code

public class Solution {
    /**
     * restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]
     *
     * @param restaurants
     * @param veganFriendly
     * @param maxPrice
     * @param maxDistance
     * @return* /
    public List<Integer> filterRestaurants(int[][] restaurants,
                                           int veganFriendly, int maxPrice,
                                           int maxDistance) {

        List<int[]> temp = new ArrayList<>();
        for (int[] restaurant : restaurants) {
            if ((veganFriendly == 1 && restaurant[2] != 1) || restaurant[3] > maxPrice || restaurant[4] > maxDistance) {
                continue;
            }
            temp.add(restaurant);
        }
        quickSort(temp, 0, temp.size() - 1);
        List<Integer> result = new ArrayList<>();
        for (int[] r : temp) {
            result.add(r[0]);
        }
        return result;

    }


    / * * *@param o1
     * @param o2
     * @return* /
    private static int compare(int[] o1, int[] o2) {
        if (o1[1] > o2[1]) {
            return 1;
        } else if (o1[1] == o2[1]) {
            return Integer.compare(o1[0], o2[0]);
        } else {
            return -1; }}private static void quickSort(List<int[]> arr, int low, int high) {
        int i, j;
        int[] temp, t;
        if (low > high) {
            return;
        }
        i = low;
        j = high;
        // Temp is the base bit
        temp = arr.get(low);

        while (i < j) {
            // Look to the right first, descending to the left
            while (compare(temp, arr.get(j)) >= 0 && i < j) {
                j--;
            }
            // Look at the left side, and increase in order to the right
            while (compare(temp, arr.get(i)) <= 0 && i < j) {
                i++;
            }
            // Swap if the condition is met
            if(i < j) { t = arr.get(j); arr.set(j, arr.get(i)); arr.set(i, t); }}// Finally the benchmark is the swap of numbers equal to I and j
        arr.set(low, arr.get(i));
        arr.set(i, temp);
        // Recursively call the left half array
        quickSort(arr, low, j - 1);
        // Recursively call the right half of the array
        quickSort(arr, j + 1, high);
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] res = {{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}};
        print(s.filterRestaurants(res, 1.50.10));

        res = new int[] [] {{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}};
        print(s.filterRestaurants(res, 0.50.10));
    }

    private static void print(List<Integer> list){
        for (Integer integer : list) {
            System.out.print(integer + ""); } System.out.println(); }}Copy the code

conclusion

As you can see, the final time complexity is O (nlogn), and the use case runs out in 4ms, but the memory consumption is not good because we sacrificed some memory to cache the results of the first step. In actual development, time and space can be chosen according to the actual situation

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign