Интервью: поиск диапазонов всех последовательных номеров

Question

Учитывая отсортированный массив с некоторыми упорядоченными числами и некоторыми номерами без последовательности. Напишите алгоритм, который принимает этот массив в качестве ввода и возвращает список {start, end} всех последовательных чисел. У последовательных номеров есть разница только 1.

E.g. массива:

[4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27]

public class Range 
{ 
    private int begin; 
    private int end; 
    public int begin { get; set; } 
    public int end { get; set; } 
} 

Выходов (п) решение здесь кажется очевидным, но есть способ сделать это в кратчайшие сроки?

Answer 1

одно решение двигаться вперед, скажем 3 числа, в то время и увидеть разницу между ними

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

В худшем случае, где нет последовательных номеров, мы будем перебирать n/3 раза для больших N, это имеет значение.

EDIT:

В худшем случае при таком подходе, когда есть два последовательных пар чисел, где мы должны коснуться всех чисел, так что это будет O (п) в данном конкретном случае.