Переупорядочить отсортированный массив таким образом, чтобы все элементы с нечетными индексами располагались перед всеми элементами с четными индексами.
Дан отсортированный массив arr[] , состоящий из N положительных целых чисел. Задача состоит в том, чтобы переупорядочить массив таким образом, чтобы все элементы с нечетными индексами стояли перед всеми элементами с четными индексами.
Примеры:
Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}
Output: 2 4 6 8 1 3 5 7 9Input: arr[] = {0, 3, 7, 7, 10}
Output: 3 7 0 7 10
Подход: Данную проблему можно решить, изменив данный массив, взяв значение ( максимальный элемент массива + 1) в качестве опорного (скажем), а затем для первой половины массива добавьте значение (arr[oddIndex]%pivot) * развернуть по нечетным индексам oddIndex и для второй половины массива добавить значение (arr[evenIndex]%pivot)* повернуть по четным индексам evenIndex . После вышеуказанных шагов разделите каждый элемент массива на значение pivot . Ниже приведена иллюстрация того же самого:
Consider the array arr[] = {3, 7}, then the value of pivot is 7 + 1 = 8.
For the first half:
Modify the array element arr[0] = 3 + (7%8)*8 = 3+ 56 = 59.For the second half:
Modify the array element arr[1] = 7 + (59%8)*8 = 7 + 24 = 31.
Dividing each array element by the pivot modifies the array to {7, 3} which is the required result.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность : O(N), так как мы используем цикл для прохождения N раз.
Вспомогательное пространство: O(1), так как мы не используем дополнительное пространство.