java - 用于在 Java 中访问和检索已排序项目的高效集合

Question

在我的用例中，我有一个按升序排序的时间点集合..

ArrayList<Double> times=new ArrayList<Double>();
Collections.sort(times);

我想使用一个高效的结构，当我给出一个任意时间点(它可能不存在于列表中)时，它应该以 O(1) 的复杂度给我最近和列表中的最大值。

是否有任何结构或算法可以用于上述？

Answer 1

第一个明显的改进是使用 double[]，因为这将使用一小部分内存并具有更好的访问模式。这可用于 O(log N) 查找或最近的搜索，这可能是您可以实现的最佳结果。

如果您使用 HashMap ，您可以获得 O(1) 查找，但这不会为您提供最接近的值。如果您的大部分查找都是完全匹配，则可以先使用它，如果找不到匹配项，则可以使用二进制搜索。

您还可以考虑根据需要将值排序到以小时、分钟或秒为单位的“桶”中。这将有助于降低时间复杂度，具体取决于您所做的假设。