从包含键的地图中获取最近键的最快方法：5、10、15、20、25 等到 200

Question

我有几个键，分别为 5、10、15 等，最多 200 个，其中仅包含 5 的倍数。每个键都有一个连接的字符串，如下例所示：5 = test510 = test1015 = 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);

Answer 1

您不需要排序的地图。只要用一些数学来做就可以了。

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

它的工作方式是这样的。

1. 如果除以 5 的余数key为 0、1 或 2，则加 2 不会影响除以 5。余数将被舍去，乘以 5 将得到最接近的较小倍数。

2. 如果key除以 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));

      }

Answer 2

您可以使用模运算符来获取您要查找的密钥

您可以使用类似的方法来计算最近的 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

Answer 3

一种简单的方法是找到最接近给定随机数的 5 倍数，并检查该数字是否存在于地图中 ( O(1))。如果存在，则为答案，如果不存在，则答案为最大值 (200) 或最小值 (5)。

最大 200 -> 对于大于200 的数字
最小 5 -> 对于小于5的数字

对于介于两者之间的数字 -
以 143 为例，因此最接近的 5 的倍数将是 145。这很容易找到。