Программа Python для преобразования массива в максимально-минимальную форму — набор 2 (O (1) дополнительного пробела)
Учитывая отсортированный массив положительных целых чисел, перестройте массив поочередно, т.е. первый элемент должен быть максимальным значением, вторым минимальным значением, третьим вторым максимальным, четвертым вторым минимальным и так далее.
Примеры:
Input: arr[] = {1, 2, 3, 4, 5, 6, 7}
Output: arr[] = {7, 1, 6, 2, 5, 3, 4}
Input: arr[] = {1, 2, 3, 4, 5, 6}
Output: arr[] = {6, 1, 5, 2, 4, 3}
Мы обсудили решение в посте ниже:
Переставить массив в максимально-минимальной форме | Набор 1: решение, обсуждаемое здесь, требует дополнительного места, как решить эту проблему с дополнительным пространством O (1).
В этом посте обсуждается решение, требующее O(n) времени и O(1) дополнительного места. Идея состоит в том, чтобы использовать умножение и модульный трюк для хранения двух элементов в индексе.
even index : remaining maximum element. odd index : remaining minimum element. max_index : Index of remaining maximum element (Moves from right to left) min_index : Index of remaining minimum element (Moves from left to right) Initialize: max_index = "n-1" min_index = 0 // Can be any element which is more than // the maximum value in array max_element = arr[max_index] + 1 For i = 0 to n-1 If "i" is even arr[i] += (arr[max_index] % max_element * max_element) max_index-- // if "i" is odd ELSE arr[i] += (arr[min_index] % max_element * max_element) min_index++
Как работает выражение «arr[i] += arr[max_index] % max_element * max_element» ?
Цель этого выражения — сохранить два элемента по индексу arr[i]. arr[max_index] сохраняется как множитель, а «arr[i]» сохраняется как остаток. Например, в {1 2 3 4 5 6 7 8 9} max_element равен 10, и мы сохраняем 91 в индексе 0. С 91 мы можем получить исходный элемент как 91%10 и новый элемент как 91/10.
Ниже реализация вышеуказанной идеи:
Выход :
Original Array 1 2 3 4 5 6 7 8 9 Modified Array 9 1 8 2 7 3 6 4 5
Временная сложность: O(N), так как мы используем цикл для прохождения N раз.
Вспомогательное пространство: O(1), так как мы не используем дополнительное пространство.
Спасибо Saurabh Srivastava и Gaurav Ahirwar за предложение этого подхода.
Другой подход: более простой подход будет заключаться в наблюдении за позиционированием индексации максимальных и минимальных элементов. Четный индекс хранит максимальное количество элементов, а нечетный индекс хранит минимальное количество элементов. С каждым увеличением индекса максимальный элемент уменьшается на единицу, а минимальный элемент увеличивается на единицу. Можно выполнить простой обход и снова заполнить arr[].
Примечание. Этот подход действителен только тогда, когда элементы данного отсортированного массива являются последовательными, т. е. различаются на одну единицу.
Ниже приведена реализация вышеуказанного подхода:
Выход :
Original Array 1 2 3 4 5 6 7 8 9 Modified Array 9 1 8 2 7 3 6 4 5
Временная сложность: O(N), так как мы используем цикл для прохождения N раз.
Вспомогательное пространство: O(1), так как мы не используем дополнительное пространство.
Пожалуйста, обратитесь к полной статье о преобразовании массива в максимальную минимальную форму | Установите 2 (O(1) дополнительного пробела) для более подробной информации!