Количество подмассивов, которые необходимо переупорядочить для сортировки данного массива
Опубликовано: 22 Сентября, 2022
Дан массив arr[] , состоящий из первых N натуральных чисел. Задача состоит в том, чтобы найти минимальное количество подмассивов, которые необходимо переупорядочить, чтобы результирующий массив был отсортирован.
Примеры:
Input: arr[] = {2, 1, 4, 3, 5}
Output: 1
Explanation:
Operation 1: Choose the subarray {arr[0], arr[3]}, i.e. { 2, 1, 4, 3 }. Rearrange the elements of this subarray to {1, 2, 3, 4}. The array modifies to {1, 2, 3, 4, 5}.Input: arr[] = {5, 2, 3, 4, 1}
Output: 3
Подход: Данную проблему можно решить, соблюдая следующие сценарии:
- Если данный массив arr[] уже отсортирован, то выведите 0 .
- Если первый и последний элементы равны 1 и N соответственно, то необходимо отсортировать только 1 подмассив либо arr[1, N – 2], либо arr[2, N – 1] . Поэтому выведите 1 .
- Если первый и последний элементы равны N и 1 соответственно, то необходимо отсортировать 3 подмассива, т. е. arr[0, N – 2] , arr[1, N – 1] и arr[0, 1] . Поэтому выведите 3 .
- В противном случае отсортируйте два подмассива, т.е. arr[1, N – 1] и arr[0, N – 2] .
Поэтому выведите количество минимального количества подмассивов, которые необходимо переставить.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N)
Вспомогательное пространство: O(1)