如何在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 >> M,"排序+限制"方法只有O(N log(N))的复杂度.

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

Answer 1

如果必须使用Streams:

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

否则使用a PriorityQueue并自己写一个反转Comparator.插入将是O(N(log(N))并且M元素的移除将是 O(M(log(N)).不是你要求的,但可能足够接近.