如何在Java 8中找到N个数字中最大的M个数字？
IntStream可能是最简单的方法，但我只能选择最小的M数，如下所示：
public class Test { private static final int[] arr = {5, 3, 4, 2, 9, 1, 7, 8, 6}; public static void main(String[] args) throws Exception { System.out.println(Arrays.asList(IntStream.of(arr).sorted().limit(5).boxed().toArray())); } } 顺便说一句，考虑到算法的复杂性并假设N >> M，“排序+限制”方法只有O（N log（N））的复杂度。
我认为最好的复杂性可能达到O（N log（M）），但我不知道Java 8是否有这种流方法或收集器。
如果必须使用Streams：
IntStream.of(arr).sorted().skip(NM)
否则使用PriorityQueue并自己写一个反相Comparator 。 插入将是O（N（log（N））并且M元素的移除将是O（M（log（N）） 。不是你要求的，但可能足够接近。
EJP是正确的，我测试了它 – 当输入为2时产生8和9。
import java.util.stream.IntStream; public class Test { private static final int[] arr = {5, 3, 4, 2, 9, 1, 7, 8, 6}; public static void main(String[] args) throws Exception { int n = Integer.parseInt(args[0]); System.out.println("Finding "+n+" largest numbers in arr"); IntStream.of(arr).sorted().skip(arr.length-n).boxed().forEach(big -> System.out.println(big)); } }
如果您已在项目中使用google guava，则可以利用MinMaxPriorityQueue ：
Collection<..> min5 = stream.collect( toCollection(MinMaxPriorityQueue.maximumSize(5)::create) );
可以使用JDK PriorityQueue创建自定义收集器来解决您的任务：
public static Collector> maxN(Comparator comparator, int limit) { BiConsumer, T> accumulator = (queue, t) -> { queue.add(t); if (queue.size() > limit) queue.poll(); }; return Collector.of(() -> new PriorityQueue<>(limit + 1, comparator), accumulator, (q1, q2) -> { for (T t : q2) { accumulator.accept(q1, t); } return q1; }, queue -> new ArrayList<>(queue)); }
用法：
int[] arr = {5, 3, 4, 2, 9, 1, 7, 8, 6}; System.out.println(IntStream.of(arr).boxed().collect(maxN(Comparator.naturalOrder(), 2))); // [8, 9] System.out.println(IntStream.of(arr).boxed().collect(maxN(Comparator.reverseOrder(), 3))); // [3, 1, 2]
对于大数据集和小限制可能更快，因为它不排序。 如果需要排序结果，可以将排序步骤添加到排finisher 。
您可以通过创建值的直方图来实现复杂性目标：
public static IntStream maxValues(IntStream source, int limit) { TreeMap m=new TreeMap<>(); source.forEachOrdered(new IntConsumer() { int size, min=Integer.MIN_VALUE; public void accept(int value) { if(valuecount==1? null: count-1); } }); if(m.size()==limit)// no duplicates return m.keySet().stream().mapToInt(Integer::valueOf); return m.entrySet().stream().flatMapToInt(e->{ int value = e.getKey(), count = e.getValue(); return count==1? IntStream.of(value): IntStream.range(0, count).map(i->value); }); }
它创建一个从int值到其相应出现次数的映射，但是将其内容限制为所需的值数，因此，它的操作具有O(log(M))复杂度（最坏情况，如果没有重复），并且，因为对每个值执行一次操作，其总体复杂度为O(N×log(M))如您所愿。
您可以使用原始数组进行测试
int[] arr = {5, 3, 4, 2, 9, 1, 7, 8, 6}; maxValues(Arrays.stream(arr), 3).forEach(System.out::println);
但要测试一些极端情况，您可以使用包含重复项的数组
int[] arr = {8, 5, 3, 4, 2, 2, 9, 1, 7, 9, 8, 6}; // note that the stream of three max elements contains one of the two eights
如果您努力获得最大性能，使用原始数据类型用适当的数据结构替换装箱树图可能是可行的，但这将是一个次要的性能优化，因为该解决方案已经解决了复杂性问题。
顺便说一下，这个解决方案适用于任意流，即不需要知道N的值。