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

Для заданного массива arr , состоящего из N уникальных целых чисел, задача состоит в том, чтобы переупорядочить массив таким образом, чтобы элемент с индексом i массива не был средним значением соседних элементов (т. е. индексов i-1 и i+1). Любая возможная перестановка может быть возвращена.

Пример:

Input:  arr = [5, 4, 3, 2, 1]
Output:  [5, 3, 4, 2, 1]
Explanation: In the input array:
Mean(5, 3) = (5 + 3)/2 = 4,
Mean(4, 2) = (4+ 2 )/2 = 3,
Mean(3, 1) = (3 + 1)/2 = 2.
After rearranging the array as [5, 3, 4, 2, 1], now no element is the mean of adjacent elements: (5 + 4)/2 ≠ 3, (3 + 2)/2 ≠ 4, (4 + 1)/2 ≠ 2

Input: arr = [6, 9, 12, 25, 50 75]
Output:  [6, 12, 9, 25, 50, 75 ]

Подход: основное наблюдение для решения этой проблемы состоит в том, что для 3 чисел a, b и c, удовлетворяющих условию, согласно которому b не должно быть средним значением a и c, [a, b, c] не должны сортироваться. Таким образом, эту проблему можно решить, выполнив следующие действия:

• Перебрать массив от 1 до (N-1)
• Проверить, является ли (arr[i – 1] + arr[i + 1])/2 == arr[i])
• Если условие выполнено, поменяйте местами элементы arr[i] и arr[i+1]

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(1)