Минимум свопов, чтобы сделать один массив лексикографически меньше другого

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

Рассмотрим два массива arr1[] и arr2[] каждый размером N , так что arr1[] содержит все нечетные числа от 1 до 2*N, а arr2[] содержит все четные числа от 1 до 2*N в перемешанном порядке. чтобы сделать arr1[] лексикографически меньшим, чем arr2[], заменив минимальное количество соседних элементов местами.

Примеры:

Input: arr1[] = {7, 5, 9, 1, 3}  arr2[] = {2, 4, 6, 10, 8}
Output: 3
Explanation: After 1 swap operation arr1[] = {5, 7, 9, 1, 3}. 
After two swap operations on arr2[] = {6, 2, 4, 10, 8}. 
Now, arr1[] is lexicographically smaller than arr2[]. Total operations performed = 3. 

Input: arr1[] = {1, 3} arr2[]={2, 4} 
Output: 0
Explanation: arr1[] is already lexicographically smaller than arr2[]. So output = 0.

Подход: Чтобы решить проблему, следуйте следующей идее:

arr1[] will be lexicographically smaller than arr2[], when the first element of the arr1[] will be smaller than the first element of arr2[]. 

Следуйте инструкциям, чтобы решить проблему:

  • Создайте массив нечетных[] размера 2*N и сохраните позиции всех нечетных чисел, в которых они встречаются, в массиве arr1[].
  • Теперь для каждого нечетного числа проверьте ближайшее большее число в arr2[].
  • Нет. операций, необходимых для замены элементов, чтобы сделать их лексикографически меньшими, определяется выражением
    • Позиция нечетного элемента + позиция большего элемента в arr2[](четный массив), т.е. нечетный[элемент] + j
  • Сделайте это для каждого нечетного элемента и верните минимум операций, необходимых для выполнения задачи.

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

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

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