frank - 8 months ago 20

Java Question

Say I have some integers in a data structure. When I insert new number into the data structure,

I want to get the smallest difference between the new inserted elements and any other elements already in the data structure. What data structure and algorithm should I use? A O(n) solution is trivial and I want better.

Thanks.

Answer

One option would be to use a `TreeSet`

(based on `TreeMap`

), which would require several `O(lg n)`

operations. The class exposes two methods which can be used to find the element which is closest to the value you wish to insert:

public E higher(E e)

Returns the least element in this set strictly greater than the given element, or null if there is no such element.

public E lower(E e)

Returns the greatest element in this set strictly less than 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;
}
if (set.contains(val)) {
return 0;
}
// top == 6 for input of 7
// O(lg n) operation
Integer top = (Integer) ts.lower(val);
// bottom = 9 for input of 7
// O(lg n) operation
Integer bottom = (Integer) ts.higher(val);
if (top == null) {
return bottom - val;
}
if (bottom == null) {
return val - top;
}
return (bottom - val > val - top) ? val - top : bottom - val;
}
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
}
```