Лексикографическая наименьшая и наибольшая перестановка из массива, элементы которого являются максимальным префиксом

Опубликовано: 25 Февраля, 2023

Дан массив A[] размера N , где каждый элемент A[i] = max(P[0], P[1], . . ., P[i]), где P[] — перестановка, состоящая из элементов из от 1 до N, задача состоит в том, чтобы найти лексикографически наименьшую и лексикографически наибольшую перестановку, которая удовлетворяет A[] .

Примеры:

Input: A[] = {3, 4, 5, 5, 5, 7, 7}
Output: Lexicographically smallest permutation is: {3 4 5 1 2 7 6}. 
Lexicographically largest permutation is: { 3 4 5 2 1 7 6} 

Input: A[] = {2, 4, 4, 4, 6, 6}
Output: Lexicographically smallest permutation is: 2 4 1 3 6 5 
Lexicographically largest permutation is: 2 4 3 1 6 5 

Подход: Эту проблему можно решить, используя эту идею:

Use a set to store the first N natural number and for each element of A, find the lexicographical element satisfying A using property of set that it stores values in sorted order.

Чтобы создать массив перестановок, поместите все натуральные числа от 1 до N в набор, потому что каждый элемент требуется только один раз.

  • Для минимальной перестановки инициализируйте переменную curr_max значением 0 и пройдитесь по массиву:
    • Если curr_max меньше, чем A[i] , выберите A[i] и поместите его в перестановку и удалите A[i] из множества, обновив curr_max = A[i] .
    • В противном случае из набора поставьте первое число из набора в позицию, чтобы сделать перестановку лексикографически минимальной, и удалите первый элемент набора.
  • Во-вторых, для максимальной перестановки снова инициализируйте переменную curr_max значением 0 и пройдитесь по массиву:
    • Если curr_max меньше, чем A[i] , выберите A[i] и поместите его в перестановку и удалите A[i] из множества, обновив curr_max = A[i] .
    • В противном случае проверьте нижнюю границу A[i] и уменьшите итератор, чтобы получить наибольшее число, меньшее, чем A[i] в наборе, и удалите его из набора.
  • Допустим, минимальная полученная перестановка называется мини , а максимальная полученная перестановка макси , и верните это

Ниже приведена реализация описанного выше подхода.

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

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