Минимальное количество деков, необходимое для сортировки массива

Опубликовано: 21 Сентября, 2022

Дан массив arr , содержащий N уникальных целых чисел. Задача состоит в том, чтобы рассчитать минимальное количество требуемых деков сделать массив отсортированным.

Пример :

Input: arr[] = {3, 6, 0, 9, 5, 4}
Output: 2
Explanation: 
Create a new deque d1 = {3}.
Create a new deque d2 = {6}.
Push 0 onto the front of d1; d1 = {0, 3}
Push 9 onto the back of d2; d2 = {6, 9}
Push 5 onto the front of d2; d2 = {5, 6, 9}
Push 4 onto the front of d2; d2 = {4, 5, 6, 9}
Hence 2 minimum 2 deques are required.

Input: arr[] = {50, 45, 55, 60, 65, 40, 70, 35, 30, 75}
Output: 1

Подход : Вышеупомянутая проблема может быть решена жадно. Выполните следующие шаги, чтобы решить проблему:

  1. Создайте два массива fronts и backs , в которых будут храниться передние и задние элементы всех деков.
  2. Итерация для всех элементов в массиве. Для каждого элемента arr[i] текущий элемент может быть помещен в уже существующую очередь, если:
    • Существует fronts [j] , который больше, чем arr[i] , потому что это означает, что этот arr[i] может быть помещен в начало этой двухсторонней очереди. Но если между arr[i] и fronts[j] в массиве arr существует еще один элемент, то его нельзя затолкнуть, потому что заталкивание нарушит порядок элементов в деках, так что эти деки не могут быть организованы в виде отсортированного массив, даже индивидуально отсортированный.
    • Точно так же проверьте заднюю часть массива, используя вышеупомянутый шаг.
  3. Если элемент не может быть помещен в очередь, для этого элемента должна быть создана другая очередь. Поэтому поместите элемент как в передний, так и в задний массив, потому что он является и передним, и задним планом вновь созданной двухсторонней очереди.
  4. Теперь верните размер фронтов (или спинок) массива в качестве ответа на этот вопрос.

Ниже приведена реализация вышеуказанного подхода:


Временная сложность: O(N^3)
Вспомогательное пространство: O(N)

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