Найти отсутствующее целое число в последовательном отсортированном потоке

Ответ 1

Это больше, чем вы могли ожидать, но это можно сделать с помощью вызова 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

Обратите внимание, что такого рода вещи не очень сильно подходят для Stream s. Все методы обработки потока будут иметь тенденцию передавать вам каждый элемент ровно один раз, поэтому вам нужно обрабатывать все пропущенные пробелы сразу, и в конце концов вы пишете много кода, чтобы избежать простого написания цикл.

Ответ 2

Алгоритм для реализации здесь основан на этом: найти недостающее число в последовательности целых чисел, трюк заключается в следующем:

• вычислить сумму элементов в последовательности.
• вычислить сумму элементов, которые будут иметь последовательность с отсутствующим числом: это легко сделать, поскольку мы можем определить минимум, максимум и we знаете, что сумма из последовательности целых чисел, идущих от 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.

Ответ 3

Здесь решение, включающее операцию 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);

Ответ 4

Если в массиве есть только ОДИН недостающее число, и если все числа положительны, вы можете использовать алгоритм XOR, как описано в этом вопросе и его ответы:

List<String> list = Arrays.asList("N5", "N2", "N3", "N6");
int xorArray = list.stream()
        .mapToInt(p -> Integer.parseInt(p.substring(1)))
        .reduce(0, (p1, p2) -> p1 ^ p2);
int xorAll = IntStream.rangeClosed(2, 6)
        .reduce(0, (p1, p2) -> p1 ^ p2);
System.out.println(xorArray ^ xorAll); // 4

Преимущество такого подхода заключается в том, что вам не нужно использовать дополнительные структуры данных, все, что вам нужно, это пара int s.

ИЗМЕНИТЬ согласно комментариям @Holger ниже:

Это решение требует, чтобы вы знали диапазон номеров заранее. Хотя, с другой стороны, для сортировки списка и потока не требуется сортировать.

Даже если список не был отсортирован, вы все равно можете получить min и max (следовательно, диапазон) с помощью IntSummaryStatistics, но для этого потребуется дополнительная итерация.

Ответ 5

Вы можете создать объект состояния, который используется для преобразования одного входного потока в несколько потоков отсутствующих записей. Эти отсутствующие входные потоки затем могут быть плоскими, чтобы создать один вывод:

public class GapCheck {
    private String last;

    public GapCheck(String first) {
        last = first;
    }

    public Stream<String> streamMissing(String next) {
        final int n = Integer.parseInt(next.replaceAll("N", ""));
        final int l = Integer.parseInt(last.replaceAll("N", ""));
        last = next;
        return IntStream.range(l + 1, n).mapToObj(Integer::toString);
    }
} 

Использование:

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

arr.stream()
   .flatMap(new GapCheck(arr.get(0))::streamMissing)
   .forEach(System.out::println);

выход:

2
4

Ответ 6

Вот одно решение, использующее чистые потоки, хотя и не очень эффективное.

public void test() {
    List<String> arr = new ArrayList(
                    Arrays.asList("N1", "N2", "N3", "N5", "N7"));

    List<Integer> list = IntStream
                .range(1, arr.size())
                .mapToObj(t -> new AbstractMap.SimpleEntry<Integer, Integer>(
                        extract(arr, t), extract(arr, t) - extract(arr, t - 1)))
                .filter(t -> t.getValue() > 1)
                .map(t -> t.getKey() - 1)
                .collect(Collectors.toList());

    System.out.println(list);
}

private int extract(List<String> arr, int t) {
    return Integer.parseInt(arr.get(t).substring(1));
}

Основной блок производительности будет вызван повторным анализом элементов списка. Однако это решение сможет предоставить все недостающие номера.