Перестройте массив, чтобы максимизировать элементы, которые меньше, чем оба его соседних элемента.

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

Дан массив 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}. 

  1. For arr[0](= 2), is greater than the elements on both sides of it.
  2. For arr[1](= 1), is less than the elements on both sides of it.
  3. For arr[2](= 3), is less than the elements on its right and greater than the elements on its left.
  4. 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

Подход: Данная проблема может быть решена на основе следующих наблюдений:

  1. Consider the maximum number of indices that can satisfy the conditions being X.
  2. Then, at least (X + 1) larger elements are required to make it possible as each element requires 2 greater elements.
  3. 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)

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