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

Question

假设我在数据结构中有一些整数.当我在数据结构中插入新数字时,我希望获得新插入元素与数据结构中已有的任何其他元素之间的最小差异.我应该使用什么数据结构和算法？AO(n)解决方案是微不足道的,我想要更好.谢谢.

Answer 1

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

public E ceiling(E e)
返回此set中大于或等于给定元素的最小元素,如果没有这样的元素,则返回null.

public E floor(E e)
返回此set中小于或等于给定元素的最大元素,如果没有这样的元素,则返回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
}