1

我正在尝试找到一个要在我的 Java 项目中使用的数据结构。我想要做的是从一组数字中获得低于任意数字的下一个最大值，或者如果不存在这样的数字则通知。

示例 1) 我的任意数字是 7.0。{3.1, 6.0, 7.13131313, 8.0} 我需要从这个集合中得到的数字是 6.0。

示例 2）我的任意数字是 1.0。{2.0, 3.5555, 999.0} 集合中不存在下一个最高数字，所以我需要知道它不存在。

我能想到的最好的方法是通过数组进行索引和比较，一旦我遍历了我的任意数字，就返回 1 步。在最坏的情况下，虽然我的时间复杂度是 O(n)。有没有更好的办法？

4

4 回答 4

4

如果您可以预处理值列表，那么您可以对列表（O(NLogN)时间）进行排序并执行二进制搜索，该搜索将获取O(LogN)您想要获得答案的每个值。否则你不能做得比O(N).

于 2013-10-03T11:25:17.590 回答
1

You need to sort the numbers at first. And then you could do a simple binary search whose compare function modified to your need. At every point check the element is bigger than input, if so search in the left side or in the right side. Your modified binary search, at the end should be able to provide the immediate bigger and the smaller number with which you could solve your problem easily. Complexity is lg n.

于 2013-10-03T11:30:30.477 回答
1

I suggest that you look at either TreeSet.floor(...) or TreeSet.lower(...). One of those should satisfy your requirements, and both have O(logN) complexity ... assuming that you have already built the TreeSet instance.

If you only have a sorted array and don't want the overhead of building a TreeSet, then a custom binary search is the probably the best bet.

于 2013-10-03T11:31:06.043 回答
0

您的两个示例集看起来都已排序...

如果是这种情况，那么您将需要二进制搜索...如果不是这种情况，那么您需要准确地访问每个元素一次。所以这需要时间 n..

于 2016-10-25T13:12:22.193 回答