Количество подмассивов, которые необходимо переупорядочить для сортировки данного массива

Опубликовано: 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)

РЕКОМЕНДУЕМЫЕ СТАТЬИ