如何从Java8中的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，"sorted + limit" 方法的复杂性仅为 O(N log(N))。

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

Answer 1

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 2

如果必须使用流：

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

否则使用 PriorityQueue 并为自己写一个反转 Comparator。插入将是 O(N(log(N))，删除 M 个元素将是 O(M(log(N))。不是您所要求的，但也许足够接近了。

Answer 3

如果您已经在项目中使用 google 番石榴，您可以利用 MinMaxPriorityQueue:

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

Answer 4

可以使用 JDK PriorityQueue 创建自定义收集器来解决您的任务：

public static <T> Collector<T, ?, List<T>> maxN(Comparator<? super T> comparator, 
                                                int limit) {
    BiConsumer<PriorityQueue<T>, 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.

Answer 5

您可以通过创建值的直方图来实现您的复杂性目标：

public static IntStream maxValues(IntStream source, int limit) {
    TreeMap<Integer,Integer> m=new TreeMap<>();
    source.forEachOrdered(new IntConsumer() {
        int size, min=Integer.MIN_VALUE;
        public void accept(int value) {
            if(value<min) return;
            m.merge(value, 1, Integer::sum);
            if(size<limit) size++;
            else m.compute(min=m.firstKey(), (k,count)->count==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 的值。

如何从Java8中的N个数中找出最大的M个数？

How can I find the largest M numbers from N numbers in Java 8?

java

algorithm

java-8

java-stream