如何以每个元素大于/小于其邻居的方式重新排列数组

For example, if the numbers are:

例如，如果数字是：

30, 12, 49, 6, 10, 50, 13

The array will be:

该数组将是：

[10, 6, 30, 12, 49, 13, 50]

As you can see:

如你看到的：

6 is smaller than both 10 and 30 and
6小于10和30
49 is greater than 12 and 13 and so on.
49大于12和13等等。

The numbers are all different and real. I need the most efficient algorithm.

数字都是不同的和真实的。我需要最有效的算法。

4 个解决方案

#1

This can be done in O(n):

这可以在O（n）中完成：

Find median in O(n) (description is available in Wikipedia
在O（n）中找到中位数（描述可在*中找到
Put every element larger than the median on odd places and every smaller element - on even places
将每个元素大于中位数放在奇数位置和每个较小元素上 - 在偶数位置

Of course, this assumes that all elements are distinct, otherwise sometimes it will fail.

当然，这假设所有元素都是不同的，否则有时会失败。

#2

Assuming the numbers are all distinct, the easiest way is probably to sort the numbers then interleave the first and second halves of the sorted list. This will guarantee the high/low/high/low/high/low/.... pattern that you need.

假设数字都是不同的，最简单的方法可能是对数字进行排序，然后交错排序列表的前半部分和后半部分。这将保证您需要的高/低/高/低/高/低/ ....模式。

This algorithm is O(n log n) which should be efficient enough for most purposes, and may benefit from optimised sorting routines in your standard library.

该算法为O（n log n），对于大多数用途而言应该足够有效，并且可以从标准库中的优化排序例程中受益。

If the numbers are not distinct, then it is possible that there is no solution (e.g. if the numbers are all equal)

如果数字不明显，则可能没有解决方案（例如，如果数字全部相等）

#3

Someone posted this question as a dupe to this but the solution over there is better than the accepted solution here so I figured I'd post it here.

有人发布这个问题作为对此的欺骗，但那里的解决方案比这里接受的解决方案更好，所以我想我会在这里发布。

Basically the key is for every three numbers where it has to hold that a < b > c you look at the sequence and swap the biggest number into the center. Then you increment by 2 to get to the next sequence like a < b > c and do the same thing.

基本上关键是每三个数字必须保持一个 c你看序列并将最大数字交换到中心。然后你增加2来得到像 c那样的下一个序列并做同样的事情。

Technically the solution still runs in O(n) like the accepted solution, but it is a better O(n) and it is much simpler because the median of medians algo is tricky to implement. Hopefully anyone who favorited this problem will at least see this solution, I can post the code if anyone is interested.

从技术上讲，解决方案仍然在O（n）中运行，就像接受的解决方案一样，但它是一个更好的O（n）并且它更简单，因为中位数算法的中位数很难实现。希望任何支持这个问题的人至少会看到这个解决方案，如果有人感兴趣，我可以发布代码。

#4

I'm not too knowledgeable about complexity, but here's my idea.

我不太了解复杂性，但这是我的想法。

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 code:

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

Output:

输出：

*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]

#1