对数组进行排序,使得元素a [i] -a [i + 1] <= a [i + 1] -a [i + 2]的差异

Question

自从我上周开始尝试按条件对N个元素的数组进行排序时,我的思绪就被吹了:2个元素之间的差异总是小于或等于接下来的2个元素.例如:

?[4] = { 10, 2, 7, 4}

可以通过这种方式重新排列该数组:

• {2, 7, 10, 4} 因为 (2 - ­7 = ­-5) < (7 - ­10 = -­3) < (10 - ­4 = 6)

• {4, 10, 7, 2} 因为 (4 - ­10 = -­6) < (10 - ­7 = ­3) < (7 - ­2 = 5)

我考虑的一个解决方案就是改组阵列并每次检查它是否符合条件,这是一种有效的方法,适用于少量元素,但对于大量元素而言耗时甚至不可能.

另一个尝试用循环移动数组周围的元素,希望再次满足要求,但是这种方法再次非常耗时,有时也是不可能的.

试图找到一个算法似乎没有任何结果,但必须有一些东西.

非常感谢你提前.

Answer 1

并不是说，由于差异应该不断上升，所以任何解决方案都将首先按升序排列元素，然后按降序排列。两个“子顺序”中的任何一个的长度都可以为 0，因此解决方案可以由严格上升或严格下降序列组成。

以下算法将找到任何解决方案：

将集合分为两组，A 和 B。允许空集合。

按升序对 A 进行排序，按降序对 B 进行排序。

连接两个已排序的集合：AB

检查您是否有解决方案。

对所有可能的 A 和 B 划分执行此操作。