Amazon Fresh is a grocery delivery service that offers consumers the option of purchasing their groceries online and schedule future deliveries of purchased groceries. Amazon's backend system dynamically tracks each Amazon Fresh delivery truck and automatically assigns the next deliveries in a truck's plan. To accomplish this, the system generates an optimized delivery plan with X destinations. The most optimized plan would deliver to the closest X destinations from the start among all of the possible destinations in the plan. Given an array of N possible delivery destinations, implement an algorithm to create the delivery plan for the closest X destinations.
Input
The input to the function/method consists of three arguments:
numDestinations, an integer representing the total number of possible delivery destinations for the truck (N);
allLocations, a list where each element consists of a pair of integers representing the x and y coordinates of the delivery locations;
numDeliveries, an integer representing the number of deliveries that will be delivered in the plan (X).
Output
Return a list of elements where each element of the list represents the x and y integer coordinates of the delivery destinations.
Constraints
numDeliveries <= numDestinations
Note
The plan starts from the truck's location [0, 0]. The distance of the truck from a delivery destination (x, y) is the square root of x2 + y2. If there are ties then return any of the locations as long as you satisfy returning X deliveries.
Example
Input:
numDestinations = 3
allLocations = [[1, 2], [3, 4], [1, -1]
numDeliveries = 2
Output:
[[1, -1],[1,2]]
Explanation:
The distance of the truck from location [1, 2] is square root(5) = 2.236
The distance of the truck from location [3, 4] is square root(25) = 5
The distance of the truck from location [1, -1] is square root(2) = 1.414
numDeliveries is 2, hence the output is [1, -1] and [1, 2]
题意：
有n个目的地(用坐标表示)， 卡车从坐标(0,0)出发，求出送货距离最近的K个点
思路：
1. 将所有的truck (0,0) -> location 的距离一一算出来，存入PriorityQueue里去
2. 根据numDeliveries的个数决定从PriorityQueue里弹出值
复杂度分析：
Time: O(n*logn)
因为每add一个元素到PriorityQueue里，需要logn时间，而我需要将n个元素add进PriorityQueue里。
Space: O(n)
因为我将allLocations 的每个元素都放入了minHeap里
代码
1 import java.util.ArrayList; 2 import java.util.List; 3 import java.util.PriorityQueue; 4 5 public class ClosestXDestinations { 6 List<List<Integer>> ClosestXdestinations(int numDestinations, List<List<Integer>> allLocations, 7 int numDeliveries) { 8 // CORNER CASE 9 if (allLocations == null || allLocations.size() == 0 || allLocations.size() < numDeliveries) { 10 return new ArrayList<>(); 11 } 12 13 List<List<Integer>> result = new ArrayList<>(); 14 PriorityQueue<Position> minHeap = new PriorityQueue<>((o1, o2) -> o1.distance - o2.distance); 15 /* 16 PART1: add each position into minHeap 17 */ 18 for (int i = 0; i < allLocations.size(); i++) { 19 List<Integer> list = allLocations.get(i); 20 // Pythagorean Theorem 21 int distance = list.get(0) * list.get(0) + list.get(1) * list.get(1); 22 Position p = new Position(list, distance); 23 minHeap.add(p); 24 } 25 /* 26 PART2: grab the number of numDeliveries from minHeap 27 */ 28 for (int i = 0; i < numDestinations && i < numDeliveries; i++) { 29 result.add(minHeap.poll().list); 30 } 31 return result; 32 } 33 34 class Position { 35 List<Integer> list; 36 int distance; 37 38 public Position(List<Integer> list, int distance) { 39 this.list = list; 40 this.distance = distance; 41 } 42 } 43 44 /* 45 TEST CASE 46 */ 47 public static void main(String[] args) { 48 ClosestXDestinations test = new ClosestXDestinations(); 49 int numDestinations = 3; 50 int numDeliveries = 2; 51 List<Integer> list1 = new ArrayList<>(); 52 List<Integer> list2 = new ArrayList<>(); 53 List<Integer> list3 = new ArrayList<>(); 54 List<List<Integer>> allLocations = new ArrayList<>(); 55 list1.add(1); 56 list1.add(2); 57 list2.add(3); 58 list2.add(4); 59 list3.add(1); 60 list3.add(-1); 61 allLocations.add(list1); 62 allLocations.add(list2); 63 allLocations.add(list3); 64 List<List<Integer>> result = test.ClosestXdestinations(numDestinations, allLocations, numDeliveries); 65 for (int i = 0; i < result.size() ; i++) { 66 System.out.println("[" + result.get(i).get(0) + "," + result.get(i).get(1) + "]"); 67 } 68 } 69 }
注意：
这里用一个自定义类，因为我们要将distance放入PriorityQueue里面，但是又需要保留是哪个坐标对应的distance，
所以自定义类class Point的需要两个属性: List<Integer> list -- 代表当前点的坐标， int distance -- 代表当前点到卡车(0,0)的距离
转载于:https://www.cnblogs.com/liuliu5151/p/11020643.html
