java - 在顺序排序的流中查找丢失的整数

Question

假设我有一个列表

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"- 或者只是 6 -(在这个例子中)

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

Answer 1

此处实现的算法基于this one : 要在整数序列中找到缺失的数字，诀窍是:

• 计算序列中元素的总和。
• 用缺失的数字计算序列的元素总和:这很容易做到，因为我们可以确定最小值、最大值和we know。从 min 到 max 的整数序列的总和是 max*(max+1)/2 - (min-1)*min/2 。
• 找出这两个总和之间的差值:这是我们缺少的数字

在这种情况下，我们可以通过首先映射到仅由数字本身构成的 IntStream 然后调用 summaryStatistics() 来收集关于我们的 Stream 的统计信息。 .这将返回 IntSummaryStatistics它具有我们想要的所有值:最小值、最大值和总和:

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。