使用Java Stream API按降序对数组进行部分排序

Question

我需要知道如何使用Stream API按降序对原始唯一整数数组进行部分排序。例如，如果有一个类似的数组{1,2,3,4,5}，我想得到{5,4,3, 1,2}-首先是3个最大的元素，然后是其余的。甚至有可能使用流吗？我检查了文档-有两种方法skip，limit但是它们会更改流的内容并从数组的开头开始工作。

我可以像这样对整个数组进行排序

Arrays.stream(arr)
.boxed()
.sorted(Collections.reverseOrder())
.mapToInt(Integer::intValue)
.toArray();

但是如何使这种排序不完整？我说Stream API是因为我希望它写得很好。

我从直觉上也觉得concat可以尝试一下。我可以考虑的另一种方法-使用自定义比较器来限制排序元素的数量。你怎么看？

PS我不是Java专家。

Answer 1

这是一种使用流的方法。

int[] sortPartially(int[] inputArray, int limit) {
    Map<Integer, Long> maxValues = IntStream.of(inputArray)
                                            .boxed()
                                            .sorted(Comparator.reverseOrder())
                                            .limit(limit)
                                            .collect(Collectors.groupingBy(x -> x, LinkedHashMap::new, Collectors.counting()));

    IntStream head = maxValues.entrySet()
                              .stream()
                              .flatMapToInt(e -> IntStream.iterate(e.getKey(), i -> i)
                                                          .limit(e.getValue().intValue()));

    IntStream tail = IntStream.of(inputArray)
                              .filter(x -> {
        Long remainingDuplication = maxValues.computeIfPresent(x, (y, count) -> count - 1);
        return remainingDuplication == null || remainingDuplication < 0;
    });

    return IntStream.concat(head, tail).toArray();
}

上面的示例当然对整个输入数组进行排序，但保持未排序元素的顺序稳定。

使用优先级队列的另一个流示例（如其他人提到的）降低了运行时复杂性：

Collection<Integer> sortPartially(int[] inputArray, int sortedPartLength) {
    Queue<Integer> pq = new PriorityQueue<>(sortedPartLength);

    Deque<Integer> result = IntStream.of(inputArray).boxed().map(x -> {
        pq.add(x);
        return pq.size() > sortedPartLength ? pq.poll() : null;
    }).filter(Objects::nonNull).collect(Collectors.toCollection(ArrayDeque::new));

    Stream.generate(pq::remove).limit(sortedPartLength).forEach(result::addFirst);

    return result;
}

如果输入数组中存在重复项，则未排序元素的顺序可能会更改。