Перестройте массив, чтобы максимизировать элементы, которые меньше, чем оба его соседних элемента.
Дан массив arr[] , состоящий из N различных целых чисел, задача состоит в том, чтобы переставить элементы массива так, чтобы количество элементов, которые меньше, чем их соседние элементы, было максимальным.
Примечание . Элементы слева от индекса 0 и справа от индекса N-1 рассматриваются как -INF.
Примеры:
Input: arr[] = {1, 2, 3, 4}
Output: 2 1 3 4
Explanation:
One possible way to rearrange is as {2, 1, 3, 4}.
- For arr[0](= 2), is greater than the elements on both sides of it.
- For arr[1](= 1), is less than the elements on both sides of it.
- For arr[2](= 3), is less than the elements on its right and greater than the elements on its left.
- For arr[4](= 1), is greater than the elements on both sides of it.
Therefore, there is a total of 1 array element satisfying the condition in the above arrangement. And it is the maximum possible.
Input: arr[] = {2, 7}
Output: 2 7
Подход: Данная проблема может быть решена на основе следующих наблюдений:
- Consider the maximum number of indices that can satisfy the conditions being X.
- Then, at least (X + 1) larger elements are required to make it possible as each element requires 2 greater elements.
- Therefore, the maximum number of elements that is smaller than their adjacent is given by (N – 1)/2.
Выполните следующие шаги, чтобы решить проблему:
- Инициализируйте массив, скажем, temp[] размера N , в котором хранится переупорядоченный массив.
- Отсортируйте заданный массив arr[] в порядке возрастания.
- Выберите первые (N – 1)/2 элемента из массива arr[] и разместите их по нечетным индексам в массиве temp[] .
- Выберите остальные (N + 1)/2 элементы из массива arr[] и поместите их в оставшиеся индексы в массиве temp[] .
- Наконец, после выполнения вышеуказанных шагов напечатайте массив temp[] в качестве результирующего массива.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O (N * log (N))
Вспомогательное пространство: O(N)