12

例如，如果数字是：

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

该数组将是：

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

如你看到的：

  • 6 小于 10 和 30 并且
  • 49 大于 12 和 13 等等。

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

4

4 回答 4

15

这可以在 O(n) 中完成：

  1. 在 O(n) 中查找中位数（描述可在Wikipedia中找到
  2. 将每个大于中位数的元素放在奇数位置，将每个较小的元素放在偶数位置

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

于 2013-05-26T15:40:23.817 回答
14

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

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

如果数字不是不同的，那么可能没有解决方案（例如，如果数字都相等）

于 2013-05-25T09:24:41.297 回答
1

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

基本上，关键是对于必须保持的每三个数字，a < b > c您查看序列并将最大的数字交换到中心。然后你增加 2 以进入下一个序列a < b > c并做同样的事情。

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

于 2013-07-22T17:28:44.080 回答
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]

哈斯克尔代码：

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]
于 2013-05-26T13:02:39.667 回答