在Java 8中，如何从N个数字中找到最大的M个数字？

Question

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

我认为最好的复杂性可能达到O（N log（M）），但我不知道Java 8是否有这种流方法或收集器。

Answer 1

如果您已经在项目中使用google guava，您可以利用MinMaxPriorityQueue：

Collection<..> min5 = stream.collect(
    toCollection(MinMaxPriorityQueue.maximumSize(5)::create)
);

Answer 2

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));
    }
}

Answer 3

如果必须使用流：

IntStream.of(arr).sorted().skip(N-M)

否则，使用优先级队列（PriorityQueue）并编写一个反向比较器（inversing Comparator）。插入为O（N（log（N）），移除M个元素为O（M（log（N））。不是你想要的，但可能足够近了。