1

I have a static set of ordered numbers {1, 2, 4, 10, 14, 20, 21,24, 29, 30} that can be stored in any collections. If a new number is passed in, I need to be able to find the nearest greater number to the new number.

For example: If my static set of ordered number is {1, 2, 4, 10, 14, 20, 21,24, 29, 30}. The number passed in is 23, the closest greater number is 24.

I thought about storing the static numbers into an array. Looping the array and then trying to find the closest number but this solution is O(n). Is there a quicker way?

4

3 回答 3

3

假设整数数组已排序，那么您可以使用Arrays.binarySearch(array, key).

调用的结果binarySearch要么是数组中键的偏移量，要么是“插入点”；即需要插入密钥的偏移量。如果您得到一个插入点（表示为负数），您可以使用它来识别数组中的下一个最大或下一个最小数字。（“插入点”的确切含义和表示在 javadoc 中进行了解释。）

这个过程的复杂性将是O(logN)。

这将比使用更快，Collections.binarySearch因为后者需要在将其包装在列表中之前将其转换int[]为 an 。Integer[]如果你从一个 开始Integer[]，有一个替代的重载Arrays.binarySearch将适用于任何对象数组。

它也比TreeSet从输入数组创建一个更快。但是，TreeSet 的优点是一旦创建了集合，更新将更便宜……与基于数组或基于数组列表的表示相比。（但更新不是上述要求的一部分。）

于 2013-10-27T02:33:40.163 回答
3

在 Java 1.6 中，有NavigableSet接口。TreeSet 和 ConcurrentSkipListSet 都实现了这个接口。它是 SortedSet 的子接口，旨在取代 SortedSet。

所以，你现在已经在这个 NavigableSet 中获得了你的集合。您现在有两种方法 - floor和ceiling分别返回小于或大于参数的元素，如果有一个，则返回相等，如果没有这样的元素，则返回 null。

有了这个，你可以做一些事情：

int closest(int arg) {
    Integer ceil = set.ceiling(arg);
    Integer floor = set.floor(arg);

    if(ceil == null) { return floor; }
    if(floor == null) { return ceil; }

    int cdiff = ceil - arg;
    int fdiff = arg - floor;

    if(cdiff < fdiff) { return ceil; }
    else { return floor; }
}

意识到对于小型阵列，此实现与其他实现之间的速度差异可能可以忽略不计。

如果您正在处理大量数字，您可能希望考虑使用双重链接的底层实现自己的跳过列表（它是一种简洁的数据结构）。然后，您可以到达该值应该在的位置（如果不是），并轻松地向上或向下移动底层以获得下一个更高和更低的数字。

于 2013-10-27T03:14:16.917 回答
0

如果您有有序列表，则可以将其放在 List 中并调用Collections.binarySearch(list, valueToCheck)

如果返回索引为负数，则需要将其转换为相应的正数索引，并确保该数字大于传入的数字（应该将其转换为正数，请注意它是否大于列表中的最后一个数字）。

于 2013-10-27T02:01:16.853 回答