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

Question

我有几个键，分别为 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);

Answer 1

您不需要排序的地图。只要用一些数学来做就可以了。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;long&nbsp;key&nbsp;=&nbsp;((key&nbsp;+&nbsp;2)&nbsp;/&nbsp;5)&nbsp;*&nbsp;5它的工作方式是这样的。如果除以 5 的余数key为 0、1 或 2，则加 2 不会影响除以 5。余数将被舍去，乘以 5 将得到最接近的较小倍数。如果key除以 5 的余数为 3 或 4，则在进行相同的除法和乘法后，加上 2 会将其推至下一个更高的倍数。&nbsp; &nbsp; &nbsp;Map<Long, String> map = new HashMap<>();&nbsp; &nbsp; &nbsp; map.put(5L, "a");&nbsp; &nbsp; &nbsp; map.put(10L, "b");&nbsp; &nbsp; &nbsp; map.put(25L, "e");&nbsp; &nbsp; &nbsp; map.put(20L, "d");&nbsp; &nbsp; &nbsp; map.put(15L, "c");&nbsp; &nbsp; &nbsp; map.put(30L, "f");&nbsp; &nbsp; &nbsp; map.put(0L, "g");&nbsp; &nbsp; &nbsp; Random r = new Random();&nbsp; &nbsp; &nbsp; for (int i = 0; i < 20; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;long key = r.nextInt(31);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;long save = key;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// simple calculation that guarantees nearest multiple of 5.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;key = ((key + 2) / 5) * 5;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;System.out.printf("Random = %3d,&nbsp; key = %3d, value = %s%n", save,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;key, map.get(key));&nbsp; &nbsp; &nbsp; }

Answer 2

您可以使用模运算符来获取您要查找的密钥您可以使用类似的方法来计算最近的 5 倍数键。public Long getNearestKey(Long random) {&nbsp; &nbsp;Long modulus = random % 5;&nbsp; &nbsp;Long key = modulus < 3 ? random - modulus : random + (5 - modulus);&nbsp; &nbsp;return key;}然后在您调用的方法中getNearestKey(42L)，它将返回最接近的值。一个简单的测试：public static void main(String[] args) {&nbsp; &nbsp; for(long i = 400; i <= 405; i++)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(getNearestKey(i));}public static Long getNearestKey(Long random) {&nbsp; &nbsp; Long modulus = random % 5;&nbsp; &nbsp; Long key = modulus < 3 ? random - modulus : random + (5 - modulus);&nbsp; &nbsp; return key;}输出：400400&nbsp;400405405405

Answer 3

一种简单的方法是找到最接近给定随机数的 5 倍数，并检查该数字是否存在于地图中 ( O(1))。如果存在，则为答案，如果不存在，则答案为最大值 (200) 或最小值 (5)。最大 200 -> 对于大于200 的数字最小 5 -> 对于小于5的数字对于介于两者之间的数字 -以 143 为例，因此最接近的 5 的倍数将是 145。这很容易找到。