在不到 O(n) 的时间内获得数据结构中元素之间的最小差异

Get the smallest difference between elements in a data structure in less than O(n) time

假设我在数据结构中有一些整数。当我将新数字插入数据结构时, 我想获得新插入的元素与数据结构中已有的任何其他元素之间的最小差异。我应该使用什么数据结构和算法? O(n) 解决方案很简单,我想要更好的解决方案。 谢谢。

您可以使用 height-balanced binary search tree。这些可以使用多种数据结构中的一种来实现。插入通常是平均 O(log(n)) 并且查找一个或两个最接近的整数(在插入值的任一侧)也将最多为 O(log(n)).

可能还有其他数据结构可以做得更好(特别是如果您可以合理地绑定需要处理的整数值),但我想不出一个。

一种选择是使用 TreeSet(基于 TreeMap),这需要多次 O(lg n) 操作。 class 公开了两种方法,可用于查找最接近您要插入的值的元素:

public E ceiling(E e)
Returns the least element in this set greater than or equal to the given element, or null if there is no such element.

public E floor(E e)
Returns the greatest element in this set less than or equal to the given element, or null if there is no such element.

public static int findClosest(TreeSet set, Integer val) {
    if (set == null || set.size() == 0) {
        return -1;
    }

    // ceiling == 9 for input of 7
    // O(lg n) operation
    Integer ceiling = (Integer)set.ceiling(val);
    // floor = 6 for input of 7
    // O(lg n) operation
    Integer floor = (Integer)set.floor(val);

    if (ceiling == null) {
        return val - floor;
    }
    if (floor == null) {
        return ceiling - val;
    }

    return (val - floor > ceiling - val) ? ceiling - val : val - floor;
}

public static void main(String[] args) {
    TreeSet<Integer> ts = new TreeSet<>();
    ts.add(5);
    ts.add(1);
    ts.add(6);
    ts.add(9);
    ts.add(2);
    ts.add(3);

    int diff = findClosest(ts, 7);
    // closest is 6, so diff == 1
}