小编典典

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

algorithm

例如,如果数字为:

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

该数组将是:

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

如你看到的:

  • 6小于10和30
  • 49大于12和13,依此类推。

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


阅读 306

收藏
2020-07-28

共1个答案

小编典典

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

  1. 在O(n)中查找中位数(说明可在Wikipedia中找到
  2. 将大于中位数的每个元素放在奇数个位置,将每个较小的元素-放在偶数位置

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

2020-07-28