Свернуть последовательные числа в диапазоны

83. Свернуть последовательные числа в диапазоны

Условие задачи:
Дан массив целых чисел без повторяющихся элементов.

Необходимо отсортировать числа и преобразовать массив в строку, объединяя соседние по числовому ряду значения в диапазоны.

Примеры:

[1,4,5,2,3,9,8,11,0,13] → "0-5,8-9,11,13"
[3,1,5]                   → "1,3,5"
[1,3,5]                   → "1,3,5"
[]                        → ""
[7]                       → "7"

Код:

public class Template2 {

    public static String compress(int[] array) {
        // Реализовать
        return "";
    }
}

Спойлеры к решению

Подсказки

💡 Сначала отсортируй массив.
💡 Храни начало текущего диапазона и последний просмотренный элемент.
💡 Если следующее число не является соседним, текущий диапазон нужно добавить в результат.
💡 Если начало и конец диапазона совпадают, выводи только одно число.

Решение

import java.util.Arrays;

public class Template2 {

    public static String compress(int[] array) {
        if (array == null || array.length == 0) {
            return "";
        }

        Arrays.sort(array);

        StringBuilder result = new StringBuilder();

        int start = array[0];
        int end = array[0];

        for (int i = 1; i < array.length; i++) {
            if ((long) array[i] == (long) end + 1) {
                end = array[i];
            } else {
                appendRange(result, start, end);
                start = array[i];
                end = array[i];
            }
        }

        appendRange(result, start, end);

        return result.toString();
    }

    private static void appendRange(
            StringBuilder result,
            int start,
            int end
    ) {
        if (result.length() > 0) {
            result.append(",");
        }

        if (start == end) {
            result.append(start);
        } else {
            result.append(start)
                    .append("-")
                    .append(end);
        }
    }
}

После сортировки:

[1,4,5,2,3,9,8,11,0,13]

→

[0,1,2,3,4,5,8,9,11,13]

Последовательные значения объединяются:

0,1,2,3,4,5 → 0-5
8,9         → 8-9
11          → 11
13          → 13

Результат:

0-5,8-9,11,13

Сортировка занимает O(n log n), последующий проход — O(n).