gpt4 book ai didi

java - 使用 java map 进行范围搜索

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:41:11 33 4
gpt4 key购买 nike

我有一个用例,如果一个数字介于 0-10 之间,它应该返回 0,如果它位于 11-20 之间,它应该返回 1 等等

0 => 0-3, (0 and 3 are inclusive)
1 => 4-15, (4 and 15 are inclusive)
2 => 16-40, (16 and 40 are inclusive)
3 => 41-88, (41 and 88 are inclusive)
5 => 89-300 (89 and 300 are inclusive)

我在想我该如何实现并在考虑 java 映射,但它不允许范围搜索

我对这样的东西很感兴趣,我有一个函数

int foo() {

}

如果 foo 返回 5,因为它位于 0 到 10 之间,我会使用 0,如果 foo 返回 25,它会使用 2。

任何想法

编辑:实际上范围并不像 0-10、11-20 那么简单。我希望能够进行范围搜索。抱歉造成困惑。根据查询我添加了正确的例子,数字是连续的

最佳答案

对于范围不均匀且存在“漏洞”的更普遍的问题,我可以想到许多可能的解决方案。最简单的是:

  1. 简单地为所有有效的键值填充一个映射,多个键映射到同一个值。假设您使用 HashMap,这应该是最省时的(O(1) 查找),尽管您在设置时有更多工作并且使用了更多空间。
  2. 使用 NavigableMap 并使用 floorEntry(key) 进行查找。这应该是时间效率较低(O(log(N) 查找)但空间效率更高。

这是一个使用 NavigableMaps 的解决方案,它允许在映射中存在“漏洞”。

private static class Range {
public int upper, value;
...
}

NavigableMap<Integer, Range> map = new TreeMap<Integer, Range>();
map.put(0, new Range(3, 0)); // 0..3 => 0
map.put(5, new Range(10, 1)); // 5..10 => 1
map.put(100, new Range(200, 2)); // 100..200 => 2

// To do a lookup for some value in 'key'
Map.Entry<Integer,Range> entry = map.floorEntry(key);
if (entry == null) {
// too small
} else if (key <= entry.getValue().upper) {
return entry.getValue().value;
} else {
// too large or in a hole
}

另一方面,如果没有“漏洞”,解决方案会更简单:

NavigableMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
map.put(0, 0); // 0..4 => 0
map.put(5, 1); // 5..10 => 1
map.put(11, 2); // 11..200 => 2

// To do a lookup for some value in 'key'
if (key < 0 || key > 200) {
// out of range
} else {
return map.floorEntry(key).getValue();
}

关于java - 使用 java map 进行范围搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50655988/

33 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com