在小于O(n)时间内求出数据结构中元素之间的最小差

Question

假设我在一个数据结构中有一些整数。当我在数据结构中插入新的数字时，我希望得到新插入的元素与数据结构中已经存在的任何其他元素之间的最小差异。我应该使用什么数据结构和算法？O(n)解是平凡的，我想要更好。谢谢。

Answer 1

一种选择是使用TreeSet (基于TreeMap)，这将需要几个O(lg n)操作。该类公开两个方法，用于查找最接近您希望插入的值的元素：

公共E上限(E e) 返回此集合中大于或等于给定元素的最小元素，如果没有这样的元素，则返回null。 公共E层(E e) 返回此集合中小于或等于给定元素的最大元素，如果没有这样的元素，则返回null。

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
}

Answer 2

你可以用高度平衡二叉树。这些可以用许多数据结构中的一种实现。插入通常是O(log(n))，查找一个或两个最近的整数(插入值的两边)最多也是O(log(n))。

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