Минимум свопов, чтобы сделать один массив лексикографически меньше другого
Рассмотрим два массива 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)