我有一个未排序的对象集合[可比较],是否可以在不必调用排序的情况下获得列表集合的子列表?
我在考虑是否可以使用有限容量的 SortedList,但这看起来不是正确的选择。
我可以很容易地写出这个,但我想知道是否有另一种方法。
我无法修改现有集合的结构。
最佳答案
因为你不想调用 sort()
,您似乎正试图避免 O(n log(n)) 运行时成本。 实际上有一种方法可以在O(n) 时间内做到这一点 -- 您可以使用 selection algorithm .
在 Guava 库(Google 的核心 Java 库)中有一些方法可以做到这一点;看Ordering
并 checkout :
-
public <E extends T> List<E> Ordering.leastOf(Iterable iterable, int k)
-
public <E extends T> List<E> Ordering.greatestOf(Iterable iterable, int k)
这些是 quickselect 的实现, 因为它们是通用的,你可以在你的 Set
上调用它们并获取 k
的列表最小的东西。如果您不想使用整个 Guava 库,文档链接到源代码,我认为将这些方法移植到您的项目应该很简单。
如果你不想偏离标准库太远,你总是可以使用像TreeSet
这样的排序集。 ,尽管这会让您获得对数插入/删除时间,而不是基于散列的 Set
的出色 O(1) 性能,最后变成了 O(n log(n))。其他人提到使用堆。这也会让你O(n log(n)) 运行时间,除非你使用一些fancier heap variants .有一个 fibonacci heap implementation in GraphMaker如果您正在寻找其中之一。
其中哪些有意义实际上取决于您的项目,但我认为这涵盖了大部分选项。
关于java - 获取集合中 N 个最小的 [Comparable] 项,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5468021/