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

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" - or just 6 -(在此示例中)

它必须使用java标准流的库,不使用第三方.

Answer 1

这里实现的算法基于这一点:在整数序列中找到缺失的数字,诀窍是:

• 计算序列中元素的总和.
• 计算序列将与缺少的元素数量的总和:这是很容易做到,因为我们能够确定最小,最大和我们知道,从整数序列的总和,从去min到max的max*(max+1)/2 - (min-1)*min/2.
• 找到这两个总和之间的差异:这是我们缺少的数字

在这种情况下,我们可以Stream通过首先映射到IntStream仅由数字本身形成然后调用来收集我们的统计数据summaryStatistics().这将返回包含IntSummaryStatistics我们想要的所有值的值:min,max和sum:

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.

Answer 2

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

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);

Answer 3

这比您预期的工作量要多，但可以通过调用来完成collect。

public class Main {
    public static void main(String[] args) {
        ArrayList<String> arr = new ArrayList<String>(Arrays.asList("N1", "N2", "N3", "N5", "N7", "N14"));

        Stream<Integer> st = arr.stream().map(p -> Integer.parseInt(p.substring(1))).sorted();
        Holder<Integer> holder = st.collect(() -> new Holder<Integer>(), 
                (h, i) -> {
                    Integer last = h.getProcessed().isEmpty() ? null : h.getProcessed().get(h.getProcessed().size() - 1);
                    if (last != null) {
                        while (i - last > 1) {
                            h.getMissing().add(++last);
                        }
                    }
                    h.getProcessed().add(i);
                }, 
                (h, h2) -> {});
        holder.getMissing().forEach(System.out::println);
    }

    private static class Holder<T> {
        private ArrayList<T> processed;
        private ArrayList<T> missing;

        public Holder() {
            this.processed = new ArrayList<>();
            this.missing = new ArrayList<>();
        }

        public ArrayList<T> getProcessed() {
            return this.processed;
        }

        public ArrayList<T> getMissing() {
            return this.missing;
        }
    }
}

这打印

4
6
8
9
10
11
12
13

请注意，这种事情并不是特别适合Streams。所有流处理方法都会倾向于将每个项目精确地传递给您一次，因此您需要一次处理所有缺失数字的运行，最后，您编写了大量代码以避免只编写环形。