@cicatrix
было бы большой ошибкой думать

Как определить непрерывность значений массива и найти разрывы?

Есть предварительно отсортированный массив A из N целочисленных значений.
Требуется определить является ли он непрерывным, т.е. A[n+1] = A[n]+1 и разбить этот массив на подмассивы, где бы это условие соблюдалось.

Пока ничего в голову, кроме тупого перебора на проверку условия A[n+1] = A[n]+1 не пришло, хотел спросить, есть ли более быстрые способы?
  • Вопрос задан
  • 241 просмотр
Решения вопроса 2
mindtester
@mindtester
http://iczin.su/hexagram_48
шаг значения фиксированный?
это "1" ?

двоичный поиск вам в руки. вы же можете предсказать значение любого
A[n]
как исходного массива, так и фрагмента. по отклонению можно делать вывод о наличии пропуска (или нескольких)

надо помнить, что двиочная выборка будет эффективна в плане определения непрерывных фрагментов, для уточнения разрывов, может потребоваться эвристическая модификация алгоритма

ps SharuPoNemnogu точно!.. в общем случае, все рассуждения об арифметической прогрессии и двоичном поиске, верны для любого шага прогрессии (не только 1)
Ответ написан
Комментировать
@SharuPoNemnogu
не язык плохой, программисты такие...
это арифметическая прогрессия. Сумму элементов массива сравниваем с суммой прогрессии, если не равны запускаем двоичный поиск как написал mindtester , внутри можно так же чекать суммы
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы