Блог

У меня такая проблема:

я должен разработать алгоритм, который получает массив int и переставляет элементы, соответствующие этим ограничениям:

Для каждого элемента, должен быть ниже, чем его соседи или больше, чем его соседи:

 for each x in array a,
( a[x-1]<=a[x] AND a[x 1]<=a[x] )
OR
( a[x-1]>=a[x] AND a[x 1]>=a[x] )
  

Все это в тете (n log n) в худшем случае

Я понятия не имею, как это сделать, моя единственная интуиция заключается в том, что я должен сделать что-то похожее на сортировку слиянием…

Извините за плохой английский

1. Сортировка массива

2. Разрежьте его пополам

3. Поместите элементы из первой половины между элементами второй половины

4. Если количество элементов не равно, переместите последний элемент вперед

Пример:

1. 2 3 1 5 7 8 6 4 9

2. 1 2 3 4 5 6 7 8 9

3. 1 5 2 6 3 7 4 8 9

4. 9 1 5 2 6 3 7 4 8

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

Пример:

Ввод: 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 (уже отсортирован)

Группы: (9 9) (8 8) (7 7) (6 6) (5 5) (4 4) (3 3) (2 2) (1 1)

Группы попарно переключаются: (8 8) (9 9) (6 6) (7 7) (4 4) (5 5) (2 2) (3 3) (1 1)

Первая группа переместилась в конец: (9 9) (6 6) (7 7) (4 4) (5 5) (2 2) (3 3) (1 1) (8 8)

Возможно, идею можно усовершенствовать, чтобы получить лучший алгоритм.