我遇到了一个需要帮助的问题 - 假设我有一些由键(整数)和值(也是整数)组成的数据集。我需要能够，给定某个键的值，找到它所属的最小键范围(即找到最接近的较大和较小的键)，然后通过插值返回匹配值。我想知道哪种方式可以让我在最快的时间内做到这一点(空间复杂性不那么重要)。此外，删除是无关紧要的，所有值都是在启动时给出的(我们可以假设启动后不会再添加任何值)。我的重点是搜索时间，而不是插入时间。
最基本的解决方案是保留一个排序的键数组并对其使用二分搜索 - 直到找到输入键或找到两个大于和小于输入键的相邻元素。此选项将花费 O(log n) 进行插入和搜索。我想知道是否还有更好的。
谢谢!
最佳答案
我会使用 NavigableMap，例如 TreeMap。
NavigableMap<Integer, Integer> map = new TreeMap<>();
map.put(1, 10);
map.put(0, -10);
map.put(5, 25);
map.put(3, 20);
// find the value below.
int key = 2;
Map.Entry<Integer, Integer> entry1 = map.floorEntry(key);
Map.Entry<Integer, Integer> entry2 = map.ceilingEntry(key);
System.out.println(key + " is between " + entry1 + " and " + entry2);
打印
2 is between 1=10 and 3=20
插入、更新、查找和删除的时间复杂度为O(log N)
关于java - 以最小的复杂性将值匹配到最接近的值范围，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12074713/