Как посчитать группы целых чисел в массивах, не сортируя массив?

Question

Моя цель - иметь возможность подсчитывать группы одного и того же целого в массиве Например, в массиве, подобном этому, {1, 1, 1, 2, 2, 3, 1, 1}, есть 4 группы :

• как минимум размера 1: 3 группы
• группы не менее 2: 1
• размером не менее 3

У меня проблемы с выполнением этого без сортировки массива. Когда он сортируется, я теряю счет группы из двух единиц в конце массива, так как он помещается рядом с другими группами единиц.

int result = (int) Stream.of(1, 1, 1, 2, 1, 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 5, 4, 4, 4, 6)
        .collect(Collectors.groupingBy(i -> i))
        .entrySet().stream()
        .filter(entry -> entry.getValue().size() >= 1) // specify the size
        .count()

return result;

Этот ожидаемый результат для каждого размера следующий:

size 1 count == 8

size 2 count == 5

size 6 count == 1

size 8 count == 1

Фактический вывод выглядит следующим образом:

size 1 count == 6

size 2 count == 3

size 6 count == 2

size 8 count == 1

Разница является результатом сортировки массива до начала подсчета. Есть ли способ сделать это?

Edit: Группа - это, по сути, любое место, где повторяется одно и то же целое число до тех пор, пока перед ним не появится целое число другого значения; Итак, группы размера 2 в этом коде в этом коде являются любыми с индексами 0-2 (включительно), индексами 4-5 (включительно), индексами 6-15 (включительно, индексами 16-18 (включительно) и индексами 20-22 (включительно). Так как есть 5 групп, которые имеют размер не менее 2, следует вернуть количество 5.

императивный стиль кода для моей цели.

Scanner key = new Scanner("1 1 1 2 1 1 3 3 3 3 3 3 3 3 3 3 4 4 4 5 4 4 4 6");

        int cnt = 0;
        int counter = 0;
        int i = 0;

            while(key.hasNextInt()) {   
                int next = key.nextInt();

                if(next == array[i]) {
                    counter++;
                }

                if(i + 1 < array.length && i -1 >= 0 
                   && counter >=size  
                   && next != array[i + 1] 
                   && next == array[i-size + 1]) {
                    cnt++;
                    counter = 0;
                }
                i++;
            }
        return cnt;

Ожидаемый доход для этого такой же, как указано выше.

Фактический доход:

size 1 count == 7

size 2 count == 5

size 6 count == 3

size 8 count == 1

Проблема с этим циклом заключается в том, что он пропускает первую часть и конечную часть массива.

У меня нет такой же проблемы сортировки, как у Stream .

В идеале для этого не потребуется никаких внешних утилит / библиотек .

Answer 1

Сначала я бы предложил найти все подгруппы. Для этого вы можете использовать Stream.collect() с пользовательским коллектором:

List<List<Integer>> sublists = IntStream.of(1, 1, 1, 2, 1, 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 5, 4, 4, 4, 6)
        .collect(ArrayList::new, (lists, value) -> {
            if (lists.isEmpty() || lists.get(lists.size() - 1).stream().noneMatch(e -> e == value)) {
                lists.add(new ArrayList<>());
            }
            lists.get(lists.size() - 1).add(value);
        }, (l1, l2) -> {
            throw new RuntimeException("not supported for parallel streams");
        });

Результат:

[[1, 1, 1], [2], [1, 1], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [4, 4, 4], [5], [4, 4, 4], [6]]

Теперь вы можете использовать это для группировки размеров списка:

Map<Integer, Long> result = sublists.stream()
        .collect(Collectors.groupingBy(List::size, Collectors.counting()));
result.forEach((size, count) -> System.out.println(String.format("size %s count %s", size, count)));

Находит все существующие размеры групп и печатает:

size 1 count 3
size 2 count 1
size 3 count 3
size 10 count 1

Для подсчета всех групп с минимальной длиной вы можете использовать:

Map<Integer, Long> result = IntStream.rangeClosed(1, sublists.stream().mapToInt(List::size).max().orElse(0)).boxed()
        .collect(Collectors.toMap(Function.identity(), i -> sublists.stream().filter(l -> l.size() >= i).count()));
result.forEach((size, count) -> System.out.println(String.format("size %s count %s", size, count)));

Это печатает:

size 1 count 8
size 2 count 5
size 3 count 4
size 4 count 1
size 5 count 1
size 6 count 1
size 7 count 1
size 8 count 1
size 9 count 1
size 10 count 1

Чтобы получить только предопределенный набор размеров (например, 1, 2, 6, 8), вы можете изменить последнее решение:

Map<Integer, Long> result = IntStream.of(1, 2, 6, 8).boxed()
        .collect(Collectors.toMap(Function.identity(), i -> sublists.stream().filter(l -> l.size() >= i).count()));
result.forEach((size, count) -> System.out.println(String.format("size %s count %s", size, count)));

Результат этого:

size 1 count 8
size 2 count 5
size 6 count 1
size 8 count 1

Answer 2

Прежде всего, позвольте мне начать с того, что это не совсем то, для чего создан API Stream, но, тем не менее, это возможно, возможно, не самым элегантным способом, но, тем не менее, возможно.

Вот возможное решение для вас:

1. Конвертировать все в большую строку и разбить ее так, чтобы число стало другим.
2. Теперь поток через поток и собирать группы иих количество
3. Добавьте количество групп более высокого уровня к каждой из меньших (чтобы получить логику at least of)
4. Там вы должны иметь всю необходимую информацию

Демо

String[] groups = Stream.of(1, 1, 1, 2, 1, 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 5, 4, 4, 4, 6)
        .map(String::valueOf)
        .collect(Collectors.joining(","))
        .split("(?<=(\\d))(,)(?!\\1)");

Map<Integer, Long> groupedByGroupSizes = Arrays.stream(groups)
        .map(group -> group.split(",").length)
        .collect(Collectors.groupingBy(x -> x, Collectors.counting()));

TreeMap<Integer, Long> integerLongTreeMap = new TreeMap<>(groupedByGroupSizes);
int size = integerLongTreeMap.size();

for (Integer integer : integerLongTreeMap.keySet()) {
    Long value = integerLongTreeMap.get(integer);
    integerLongTreeMap.put(integer, value + --size);
}

integerLongTreeMap.entrySet().forEach(entry -> System.out.println(String.format("of at least size %s: %s groups", entry.getKey(), entry.getValue())));

Печать

of at least size 1: 6 groups
of at least size 2: 3 groups
of at least size 3: 4 groups
of at least size 10: 1 groups

Answer 3

Если использовать StreamEx , эта опция довольно проста

IntStream s = IntStream.of(1, 1, 1, 2, 1, 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 5, 4, 4, 4, 6);
List<List<Integer>> t = IntStreamEx.of (s).boxed().groupRuns(Integer::equals).toList();
t.forEach(e -> {
  System.out.println(String.format("Group of %s - %s times", e.get(0), e.size()));
});