Программа Python для преобразования массива в максимально-минимальную форму — набор 2 (O (1) дополнительного пробела)

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

Учитывая отсортированный массив положительных целых чисел, перестройте массив поочередно, т.е. первый элемент должен быть максимальным значением, вторым минимальным значением, третьим вторым максимальным, четвертым вторым минимальным и так далее.
Примеры:

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) дополнительного пробела) для более подробной информации!

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