самый быстрый способ получить ближайший ключ от карты, которая содержит ключи: 5, 10, 15, 20, 25 и т. д. до 200 - PullRequest
Новая
       86

самый быстрый способ получить ближайший ключ от карты, которая содержит ключи: 5, 10, 15, 20, 25 и т. д. до 200

0 голосов
/ 23 октября 2019

У меня есть несколько ключей, которые идут 5, 10, 15 и т. Д., До 200, которые содержат только кратные 5. С каждым ключом есть строка, как в этом примере: 

5 = test5
10 = test10
15 = test15

У меня есть случайная переменная, которая изменяется и может быть между 0 и 500. Я хочу получить ближайший ключ и его строку, я уже нашел решение, но мне интересно, может ли быть лучшее решение, так как в этом случае используется толькократно 5. 

TreeMap<Long,String> map = new TreeMap<>();
map.put(5L,"a");
map.put(10L,"b");
map.put(25L,"e");
map.put(20L,"d");
map.put(15L,"c");
Long key = 42L;
Map.Entry<Long,String> low = map.floorEntry(key);
Map.Entry<Long,String> high = map.ceilingEntry(key);
Object res = null;
if (low != null && high != null) {
    res = Math.abs(key-low.getKey()) < Math.abs(key-high.getKey())
            ?   low.getValue()
            :   high.getValue();
} else if (low != null || high != null) {
    res = low != null ? low.getValue() : high.getValue();
}
System.out.println(res);

Ответы [ 3 ]

1 голос
/ 23 октября 2019

Вы можете использовать оператор модуля, чтобы получить ключ, который вы ищете

У вас может быть такой метод, который вычислит ближайший ключ, кратный 5. 

public Long getNearestKey(Long random) {
   Long modulus = random % 5;
   Long key = modulus < 3 ? random - modulus : random + (5 - modulus);
   return key;
}

Затем в вашем методе вы вызываете getNearestKey(42L), и он возвращает ближайшее значение.

Простой тест: 

public static void main(String[] args) {
    for(long i = 400; i <= 405; i++) 
        System.out.println(getNearestKey(i));
}


public static Long getNearestKey(Long random) {
    Long modulus = random % 5;
    Long key = modulus < 3 ? random - modulus : random + (5 - modulus);
    return key;
}

Выход: 

400
400 
400
405
405
405
1 голос
/ 23 октября 2019

Вам не нужна отсортированная карта. Просто сделайте это с некоторой математикой. 

      long key = ((key + 2) / 5) * 5

Вот как это работает.

  1. Если остаток от key при делении на 5 равен 0, 1 или 2, то добавление 2 не повлияет на деление на 5. Остаток будет отброшен, а при умножении на 5 получится ближайший нижний множитель.

  2. Если остаток от *Если 1013 *, если разделить на 5, будет либо 3, либо 4, то добавление 2 увеличит его до следующего более высокого мультипликатора после того же деления и умножения. 

      Map<Long, String> map = new HashMap<>();
      map.put(5L, "a");
      map.put(10L, "b");
      map.put(25L, "e");
      map.put(20L, "d");
      map.put(15L, "c");
      map.put(30L, "f");
      map.put(0L, "g");

      Random r = new Random();
      for (int i = 0; i < 20; i++) {
         long key = r.nextInt(31);
         long save = key;

         // simple calculation that guarantees nearest multiple of 5.
         key = ((key + 2) / 5) * 5;

         System.out.printf("Random = %3d,  key = %3d, value = %s%n", save,
               key, map.get(key));
      }
0 голосов
/ 23 октября 2019

Простым подходом может быть нахождение ближайшего кратного 5 вашему заданному случайному числу и проверка, существует ли это число на карте или нет (O (1)). Если существует, это будет ответ, если не максимум (200) или минимум (5), будет ответом.

Макс. 200 -> для чисел большечем 200 Мин. 5 -> для чисел меньше 5

Для чисел между -давайте возьмем в качестве примера 143, поэтому ближайшее кратное 5 будет 145. Это можно легко найти.

...