如何重新排列一个数组，使得每个元素都比其相邻元素大/小？

Question

如何重新排列一个数组，使得每个元素都比其相邻元素大/小？

12

例如，如果数字是：

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

数组将会是：

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

正如您所看到的：

6比10和30都小，
49比12和13大等等。

这些数字都是不同且真实的。我需要最有效率的算法。

- Peggy

5

需要所有的解决方案还是只需要第一个？ - Alex Filipovici

如果算法能够生成所有解决方案，那将是非常好的。但是这个算法必须是最高效的。 - Peggy

2

我觉得计算“所有解决方案”可能会倾向于具有O(n!)的复杂度... - Lukas Eder

2

最佳解决方案不在这里，请查看此处的解决方案。 - aaronman

4个回答

14

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

此算法的时间复杂度为 O(n log n)，对于大多数目的来说足够高效，并且可能受益于标准库中优化过的排序例程。

如果数字不是唯一的，则有可能没有解决方案（例如，如果所有数字都相等）。

- mikera

2

[2 3] 是其中一半，[1 2] 是另一半。所以 [2 1 3 2] 实际上是将这两个部分交错在一起。仅供参考，@mikera 表示他的解决方案适用于不同的数字... - zenpoy

1

取决于你先放哪一半。我会尝试提供一个反例。 - Rusty Rob

2

不必完全排序。使用快速选择（中位数）算法，您可以在O(n)中找到中位数元素，并将数组分成小和大，然后交错排列，O(n)。是的，对于实际目的而言，快速的O(n log(n))可能比慢的O(n)更好。 - A. Webb

1

@A Webb - 很好的观点，我同意不需要完整排序。尽管如果您的编程语言具有良好的排序实现（很可能？），它可能会击败手动编写的中值分区实现，并且更简单/更少错误倾向于使用。你的情况可能不同。 - mikera

@mikera，没有任何排序算法能够击败中位数查找器。 - aaronman

显示剩余6条评论

2

有人将这个问题发布为这里的重复问题，但那里的解决方案比这里接受的解决方案更好，所以我想在这里发布它。

基本上，关键是对于每三个数字，其中必须保持a < b > c，您查看序列并将最大的数字交换到中心。然后，您增加2以进入下一个序列，例如a < b > c，并执行相同的操作。

从技术上讲，该解决方案仍在O(n)中运行，就像接受的解决方案一样，但它是更好的O(n)，而且因为中位数算法很棘手，所以更简单。希望任何收藏此问题的人都能看到这个解决方案，如果有人感兴趣，我可以发布代码。

- aaronman

0

我对复杂度了解不多，但是这里是我的想法。

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]

- גלעד ברקן

这似乎不起作用。例如，对于[3,4,0,1,2]，它返回[1,0,2,4,3]，这是无效的，因为2大于0但小于4。在这种情况下，有效的解决方案可能是[0,4,1,3,2]。使用我编写的QuickCheck测试工具包找到。 - hammar

@hammar 这里有个有趣的事情：我改了一行代码，像这样：prop_correct (Distinct xs) = odd (length xs) || valid (rearrange xs) 然后我得到了这个结果：+++ OK, passed 100 tests. - גלעד ברקן

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- maxim1000 · Accepted Answer

这可以在O(n)时间内完成：

在O(n)时间内找到中位数（有关描述可在维基百科中找到）。
将比中位数大的每个元素放在奇数位置，每个小于中位数的元素放在偶数位置。

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