在顺序排序的流中查找缺失的整数

java java-8 java-stream

2022-09-04 01:41:52

假设我有一个列表

ArrayList<String> arr = new ArrayList(Arrays.asList("N1", "N2", "N3", "N5"));

我如何找到“N4”，我的意思是，我如何找到缺失的整数是4？

到目前为止，我尝试过什么

Integer missingID = arr.stream().map(p -> Integer.parseInt(p.substring(1))).sorted()
                .reduce((p1, p2) -> (p2 - p1) > 1 ? p1 + 1 : 0).get();

这不起作用，因为在这种情况下不打算以我需要的方式工作，实际上，我不知道该怎么做。如果没有丢失的数字，则下一个必须是（在此示例中）reduce"N6" - or just 6 -

它必须使用java标准流的库来完成，不使用第三方。

答案 1

这里要实现的算法基于这个算法：要在整数序列中找到缺失的数字，诀窍是：

计算序列中元素的总和。
计算序列与缺失数字的元素之和：这很容易做到，因为我们可以确定最小值，最大值，并且我们知道从到的整数序列的总和是。minmaxmax*(max+1)/2 - (min-1)*min/2
找到这两个总和之间的差异：这是我们缺失的数字

在这种情况下，我们可以收集统计数据，方法是首先映射到仅由数字本身形成的，然后调用 summaryStatistics（）。这将返回一个 IntSummaryStatistics，它具有我们想要的所有值：最小值、最大值和总和：StreamIntStream

public static void main(String[] args) {
    List<String> arr = Arrays.asList("N3", "N7", "N4", "N5", "N2");
    IntSummaryStatistics statistics = 
        arr.stream()
           .mapToInt(s -> Integer.parseInt(s.substring(1)))
           .summaryStatistics();

    long max = statistics.getMax();
    long min = statistics.getMin();

    long missing = max*(max+1)/2 - (min-1)*min/2 - statistics.getSum();
    System.out.println(missing); // prints "6" here
}

如果没有丢失的数字，这将打印 0。

答案 2

这是涉及我的免费StreamEx库中的操作的解决方案。它打印排序输入的所有缺失元素：pairMap

ArrayList<String> arr = new ArrayList(Arrays.asList("N1", "N2", "N3", "N5"));
StreamEx.of(arr).map(n -> Integer.parseInt(n.substring(1)))
                .pairMap((a, b) -> IntStream.range(a+1, b))
                .flatMapToInt(Function.identity())
                .forEach(System.out::println);

pairMap 操作允许您将流的每个相邻对映射到其他内容。在这里，我们将它们映射到跳过的数字流，然后平展这些流。

在没有第三方库的情况下，相同的解决方案是可能的，但看起来更详细：

ArrayList<String> arr = new ArrayList(Arrays.asList("N1", "N2", "N3", "N5"));
IntStream.range(0, arr.size()-1)
                .flatMap(idx -> IntStream.range(
                    Integer.parseInt(arr.get(idx).substring(1))+1,
                    Integer.parseInt(arr.get(idx+1).substring(1))))
                .forEach(System.out::println);