Напишите функцию, которая возвращает массив начальных и конечных индексов наименьшего подмассива во входном массиве, который необходимо отсортировать на месте, чтобы отсортировать весь входной массив (в порядке возрастания).
Существует подмассив, который не отсортирован по некоторой длине, которую нам нужно найти, поэтому остальная часть входного массива уже должна быть отсортирована в порядке возрастания, с этой информацией мы могли бы найти этот подмассив за O(n) временную сложность.
Мы могли бы найти несортированные значения, просто проходя по массиву один раз и проверяя, является ли текущее значение меньше или равно следующему значению или больше или равно предыдущему значению (текущее ≤ массив[i+1] или текущий ≥ массив[i-1])
Минимальное значение в несортированных значениях должно быть начальным значением несортированного массива.
Максимальное значение в несортированном значении должно быть значением End несортированного массива.
Чтобы получить индекс минимального значения, мы итерируем от Start массива до тех пор, пока не достигнем значения, которое больше минимального значения ( arr[i] ≥ минимального значения найдено в несортированном массиве)
Чтобы получить индекс максимального значения, мы итерируем от End массива до тех пор, пока не достигнем значения, которое меньше максимального значения (arr[i] ≤ максимального значения найдено в несортированном массиве)
Мы создали функцию is_out_of_order, чтобы проверить, не отсортировано ли текущее значение; если True, мы нашли несортированное значение, поэтому мы можем обновить Минимальное и максимальное значения.
И если значения Max и Min остались прежними, т.е. бесконечность после цикла, мы знаем, что в этом массиве нет несортированных значений, поэтому возвращаем [-1,-1]
Код доступен здесь.
Сложность времени составляет O(n (для начального цикла for) + n (оба объединенных цикла while посещают индекс только один раз)), поэтому O(n), n равно длина массива.
Сложность пространства составляет O(1), так как мы не используем дополнительное пространство.
