导大师

hackerrank 上一道题 我事后一查和这个一样
我给的idea  O(NlogN+M*N）time 不是最优的 还因为紧张说错了
M: queried city number
N: given city number

K: max number in the same x or y line.

It can be O(NlogK+MlogK）average time


我早早写完，花很多时间 fix compile 错误，没时间跑cases了

如感觉对您有帮助，求赏米。




补充内容 (2021-09-16 01:06 +8:00):
事后作了一个O(NlogK) time 的

public List<String> closestStraightCity(String[] citys, int[] xs, int[] ys, String[] queryCitys) {
    Map<String, int[]> cs = new HashMap<>(); // city name: (x,y)
    Map<I

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

eger, String> hi = L.get(l).higherEntry(v);
      Map.Entry<Integer, String> low = L.get(l).lowerEntry(v);
      if (hi != null) four.add(new Choice(hi.getValue(), hi.getKey() - v));
      if (low != null) four.add(new Choice(low.getValue(), v - low.getKey()));
    }
  }

  class Choice {
    String name;
    int distance;

    public Choice(String na...

share 一个solution 求米

1. public List<String> closestStraightCity(String[] citys, int[] xs, int[] ys, String[] queryCitys) {
   
2.     Map<String, int[]> cs = new HashMap<>(); // city name: (x,y)
   
3.     Map<Integer, TreeMap<Integer, String>> X = new HashMap<>();
   
4.     // x line:  y1: city2 name( < city1name)  y3: city3 name
   
5.     Map<Integer, TreeMap<Integer, String>> Y = new HashMap<>();
   
6.     // y line:  x1: city1 name, x2: city2 name
   
7. 
   
8.     int N = citys.length;
   
9.     for (int i = 0; i < N; i++) {
   
10.       int x = xs[i], y = ys[i];
    
11.       String name = citys[i];
    
12.       X.computeIfAbsent(x, k -> new TreeMap<>());
    
13.       if (!X.get(x).containsKey(y) || name.compareTo(X.get(x).get(y)) < 0) {
    
14.         X.get(x).put(y, name); // lexicographically order name
    
15.       }
    
16. 
    
17.       Y.computeIfAbsent(y, k -> new TreeMap<>());
    
18.       if (!Y.get(y).containsKey(x) || name.compareTo(Y.get(y).get(x)) < 0) {
    
19.         Y.get(y).put(x, name); // lexicographically order name
    
20.       }
    
21.       cs.put(name, new int[] {x, y});
    
22.     }
    
23. 
    
24.     List<String> r = new ArrayList<>();
    
25.     for (String c : queryCitys) {
    
26.       int x = cs.get(c)[0], y = cs.get(c)[1];
    
27.       List<Choice> four = new ArrayList<>();
    
28.       collect(X, x, y, four);
    
29.       collect(Y, y, x, four);
    
30.       Collections.sort(
    
31.           four,
    
32.           (a, b) -> {
    
33.             if (a.distance == b.distance) return a.name.compareTo(b.name);
    
34.             return a.distance - b.distance;
    
35.           });
    
36.       r.add(four.isEmpty() ? "NONE" : four.get(0).name);
    
37.     }
    
38.     return r;
    
39.   }
    
40. 
    
41.   private void collect(Map<Integer, TreeMap<Integer, String>> L, int l, int v, List<Choice> four) {
    
42.     if (L.get(l) != null) {
    
43.       Map.Entry<Integer, String> hi = L.get(l).higherEntry(v);
    
44.       Map.Entry<Integer, String> low = L.get(l).lowerEntry(v);
    
45.       if (hi != null) four.add(new Choice(hi.getValue(), hi.getKey() - v));
    
46.       if (low != null) four.add(new Choice(low.getValue(), v - low.getKey()));
    
47.     }
    
48.   }
    
49. 
    
50.   class Choice {
    
51.     String name;
    
52.     int distance;
    
53. 
    
54.     public Choice(String name, int distance) {
    
55.       this.name = name;
    
56.       this.distance = distance;
    
57.     }
    
58.   }

复制代码

谢谢分享

MlogK ...