Как изменить порядок массива таким образом, чтобы каждый элемент был больше/меньше, чем его соседи

Ответ 1

Это можно сделать в O (n):

• Найти медиану в O (n) (описание доступно в Wikipedia
• Поместите каждый элемент больше медианного на нечетные места, а каждый более мелкий элемент - на четные места

Конечно, это предполагает, что все элементы различны, иначе иногда он терпит неудачу.

Ответ 2

Предполагая, что все цифры различны, самым простым способом, вероятно, является сортировка чисел, которые чередуют первую и вторую половинки отсортированного списка. Это гарантирует, что вам нужен шаблон с высоким/низким/высоким/низким/высоким/низким/....

Этот алгоритм O(n log n), который должен быть достаточно эффективным для большинства целей и может помочь оптимизированным процедурам сортировки в стандартной библиотеке.

Если числа не различны, то возможно, что нет решения (например, если числа равны)

Ответ 3

Кто-то разместил этот вопрос как обман для этого, но решение там лучше, чем принятое решение здесь, поэтому я решил, что разместил его здесь.

В принципе, ключ для каждого трех чисел, где он должен удерживать a < b > c, вы смотрите на последовательность и свопите наибольшее число в центр. Затем вы увеличиваете на 2, чтобы перейти к следующей последовательности, например a < b > c, и сделать то же самое.

Технически решение все еще работает в O (n), как принятое решение, но оно лучше O (n), и это намного проще, потому что медиана медианов algo сложна для реализации. Надеюсь, кто-нибудь, кто предпочтет эту проблему, по крайней мере увидит это решение, я могу опубликовать код, если кому-то это интересно.

Ответ 4

Я не слишком разбираюсь в сложности, но вот моя идея.

For even length lists:

(For our odd length example, 
 put 30 aside to make the list even) 

1. Split the list into chunks of 2    => [[12,49],[6,10],[50,13]]
2. Sort each chunk                    => [[12,49],[6,10],[13,50]]
3. Reverse-sort the chunks by 
   comparing the last element of 
   one to the first element of 
   the second                         => [[12,49],[13,50],[6,10]]

For odd length lists:
4. Place the removed first element in 
   the first appropriate position     => [30,12,49,13,50,6,10]

Код Haskell:

import Data.List (sortBy)
import Data.List.Split (chunksOf)

rearrange :: [Int] -> [Int]
rearrange xs
  | even (length xs) = rearrangeEven xs
  | null (drop 1 xs) = xs
  | otherwise        = place (head xs) (rearrangeEven (tail xs))
 where place x (y1:y2:ys) 
         | (x < y1 && y1 > y2) || (x > y1 && y1 < y2) = (x:y1:y2:ys)
         | otherwise                                  = place' x (y1:y2:ys)
       place' x (y1:y2:ys) 
         | (x < y1 && x < y2) || (x > y1 && x > y2) = (y1:x:y2:ys)
         | otherwise                                = y1 : (place' x (y2:ys))
       rearrangeEven = concat 
                     . sortBy (\a b -> compare (head b) (last a)) 
                     . map sort
                     . chunksOf 2

Вывод:

*Main> rearrange [30,12,49,6,10,50,13]
[30,12,49,13,50,6,10]

*Main> rearrange [1,2,3,4]
[3,4,1,2]