1

我遇到了一个需要帮助的问题——假设我有一些由键（整数）和值（整数）组成的数据集。我需要能够给定某个键的值，找到它所属的最小键范围（即找到最近的更大和更小的键），然后通过插值返回匹配值。我想知道哪种方式可以让我在最快的时间内做到这一点（空间复杂性要小得多）。此外，删除是无关紧要的，所有值都是在启动时给出的（我们可以假设启动后不会再添加更多值）。我的重点是搜索时间，而不是插入。

最基本的解决方案是保留一个排序的键数组并对其使用二进制搜索 - 直到我找到输入键或找到两个大于和小于输入键的相邻元素。此选项需要 O(log n) 进行插入和搜索。我想知道是否有更好的。

谢谢！

4

1 回答 1

2

我会使用 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)

于 2012-08-22T13:55:14.000 回答