按成对差排序数组

Question

例如，我们有一个数组X[n] = {X0, X1, X2, ... Xn}。目标是对这个数组进行排序，使得每一对之间的差按升序排列。

例如，X[] = {10, 2, 7, 4} 答案是：

2 7 10 4
4 10 7 2

我有一些代码，但它是暴力破解的 :)

#include <stdio.h>

int main(int argc, char **argv)
{
    int array[] = { 10, 2, 7, 4 };
    int a[4];

    for(int i = 0; i < 4; i++){
        a[0] = array[i];

        for(int j = 0; j < 4; j++){
            a[1] = array[j];
            if(a[0] == a[1])
               continue;

            for(int k = 0; k < 4; k++){
                a[2] = array[k];
                if(a[0] == a[2] || a[1] == a[2])
                    continue;

            for(int l = 0; l < 4; l++){
                a[3] = array[l];
                if(a[0] == a[3] || a[1] == a[3] || a[2] == a[3])
                    continue;
                if(a[0] - a[1] < a[1] - a[2] && a[1] - a[2] < a[2] - a[3])  
                    printf("%d %d %d %d\n", a[0], a[1], a[2], a[3]);
             }
         }
     }
   }
    return 0;
 }

有没有“漂亮”的算法的想法？ :)

- selfbg

---

定义"every pair"和"difference" - Karoly Horvath

你能解释一下为什么答案是2 7 10 4和4 10 7 2吗？你所说的“每对之间的差异”是什么意思？ - taocp

7-2 = 5，10-4 = 6，5 < 6 - Hunter McMillen

所以你还没有列出所有的答案。 - Karoly Horvath

我的意思是相邻两个数字array[i]和array[i+1]之间的差值应该是递增的： 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 - selfbg

那不是通用代码..!! - MissingNumber

Answer 1

免责声明：此解决方案将通过绝对值的差异来排列项目。感谢@Will Ness。

根据“每对之间的差异按升序排列”的要求，有一个解决方案。

您只需按升序对数组进行排序O(n)*log(n)，然后从中间开始。然后您像这样安排元素：

[n/2、n/2+1、n/2-1、n/2+2、n/2-2、n/2+3 ...] 如果(n/2)th元素右侧有更多元素，则先+1

[n/2、n/2-1、n/2+1、n/2-2、n/2+2、n/2-3 ...] 否则先-1。

这里您可以获得升序成对差异。

注意！！！不能保证此算法将找到最小的差异并从其开始，但我认为这不是要求。

例如

排序后的数组：{1、2、10、15、40、50、60、61、100、101}

然后，您选择50（作为10/2=5个），60（10/2+1=6），40等等...

您将获得：{40、50、15、60、10、61、2、100、1、101}

这让您得到了差异：10、35、45、50、51、59、88、99、100

- denis-bu

---

-10,35,-45,50,-51,59,-98,99,-100 不是按升序排列的。 - Will Ness

差异由绝对值增长。关于差异的符号（或如何获得它 - 给定一对（x1，x2），您可以获得x1-x2和x2-x1）没有要求。 - denis-bu

OP在评论中提供了这些澄清。 :) - Will Ness

我明白了 :) 不同的符号很重要。 - denis-bu

无论如何，这可能对某些人有用。 - denis-bu

Answer 2

让我们来看一下。你的例子数组是 {10,2,7,4}，你展示的答案是：

2 7 10 4         
 5 3  -6     differences,  a[i+1] - a[i]

4 10 7 2
 6 -3 -5

我在这里展示了翻转的差异，这样分析会更容易。

因此，目标是让差异按降序排列。显然，一些正差值将首先出现，然后是一些负差值。这意味着数组的最大元素将出现在中间的某个位置。它左侧的正差值必须按绝对值的降序排列，右侧的负差值必须按绝对值的升序排列。

让我们以另一个数组为例：{4,8,20,15,16,1,3}。我们从排序开始：

1 3 4 8 15 16 20
 2 1 4 7  1  4      differences,  a[i+1] - a[i]

现在，将20放在中间，然后右侧必须是递增的差值。由于解决方案左侧的差值为正，因此这些值本身是升序排列的。因此，在我们选择一些值移动到最大元素的右侧后，剩余的值保持不变，而（正的）差值必须按降序排列。如果满足这些条件，则达到了解决方案。

在这里没有解决方案。可能性如下：

...  20 16 8    (no more)  left:  1 3 4 15    (diffs: 2 1 11 5) 
...  20 16 4    (no more)  left:  1 3 8 15    (diffs: 2 5 7 5)
...  20 16 3    (no more)  left:  1 4 8 15    (diffs: 3 4 7 5)
...  20 16 1    (no more)  left:  3 4 8 15  ....................
...  20 15 8    (no more)  left:  1 3 4 16
...  20 15 4    (no more)  left:  1 3 8 16
...  20 15 3    (no more)  left:  1 4 8 16
...  20 15 1    (no more)  left:  3 4 8 16
...  20 8       (no more)  left:  1 3 4 15 16
...  20 4       (no more)  left:  1 3 8 15 16
...  20 3       (no more)  left:  1 4 8 15 16
...  20 1       (no more)  left:  3 4 8 15 16
...  20         (no more)  left:  1 3 4 8  15 16

如果没有1和3，可能有多种解决方案。

- Will Ness

Answer 3

这个问题并非总是有解。例如，数组 X[] = {0, 0, 0} 无法按要求“排序”，因为两个差值始终相等。

如果这个问题有解，那么数组的值应该按左图所示进行“排序”：一些升序的值子集应该形成结果数组的前缀，然后其余所有的值应该按降序形成其后缀。且“排序”后的数组应该是凸的。

这提供了一个算法的提示：对数组进行排序，然后将其值分成两个凸子集，然后提取其中一个子集并（反向）附加到末尾。

一个简单的（部分）实现方法是：对数组进行排序，找到属于凸包的值的子集，然后检查所有剩余的值，如果它们是凸的，则将它们附加到末尾。只有当其中一个子集完全位于另一个子集下方时，此算法才有效。

如果生成的子集相交（如右侧图所示），则可以使用此算法的改进版本：将排序后的数组分成段，其中一个子集完全位于另一个子集下方（A-B，B-C），然后对于这些段中的每一个，找到凸包并检查剩余子集的凸性。请注意，右侧图中的X轴以特殊方式对应于升序排序数组中的索引；对于子集相交（A、B、C），介于相交之间的值的X坐标根据它们在结果数组中的位置进行缩放。

算法草图

1. 将数组按升序排序。
2. 从最大值开始，尝试将凸包值添加到“顶部”子集中（类似于Graham scan algorithm）。同时将所有不属于凸包的值放入“底部”子集中并检查其凸性。继续，直到所有值都适当地适合“顶部”或“底部”子集。处理完最小值后，从数组中删除其中一个子集，反转该子集，并将其附加到数组末尾。
3. 如果将某个值添加到“顶部”子集后，“底部”子集不再是凸的，则回滚上次添加并检查该值是否可以正确添加到“底部”子集中。如果不能，则停止，因为输入数组无法按所需方式“排序”。否则，交换“顶部”和“底部”子集，并继续进行步骤2（已处理的值不应在子集之间移动，任何尝试将它们移动的尝试都应导致进入步骤3）。

换句话说，我们可以处理已排序数组的每个值，从最大到最小，尝试将此值附加到两个子集之一，使得两个子集保持凸形。首先，我们尝试将新值放置在添加了先前值的子集中。这可能会使添加早期的多个值不适合于该子集 - 然后我们检查它们是否都适合于其他子集。如果是-将它们移动到其他子集，如果不是-将它们留在“顶部”子集中，但将当前值移动到其他子集。

时间复杂度

每个值最多只能添加或从“顶部”子集中删除一次，并且最多只能添加到“底部”子集中一次。对于对元素的每个操作，我们只需要检查其两个最近的前任。这意味着步骤2和3的最坏时间复杂度为O（N）。因此，总体时间复杂度取决于第1步中的排序算法。

- Evgeny Kluev

---

你的第一张和第二张图片上的X轴和Y轴是什么？ - Will Ness

@WillNess：X是已排序数组中的索引，Y是数组元素的值。 - Evgeny Kluev

这个回答太棒了！谢谢 Evgeny :) - selfbg

为什么要用凸包来讲话？简化的原理是什么？你不是只需要检查你要添加的新点是否适合“上升”或“下降”的边吗？此外，在草图的第3步中为什么只需要“回滚”一步？难道不可能需要回滚100个点才能得到答案吗？从最大值开始观察上升和下降，然后尝试添加数字是正确的。但我不明白你的答案如何具有O(N)（排序后）算法。如果我们需要回滚多次，它会给出一个O(2^n)算法。 - Knoothe

由于我目前认为这是错误的，所以我会给它一个-1。希望在进一步解释后我能够撤回它（并转换为+1 :-)). - Knoothe

@Knoothe：是的，主要的重点就是检查新点是否进入“上升”或“下降”的“子集”，我将这些“子集”称为“臂”。添加了一种算法的替代解释，其中既没有提到“凸包”也没有提到“回滚”。希望这种替代解释有助于理解为什么这是一个线性时间算法。我认为，在原始解释中使用“凸包”具有一定的优势，因为它显示了与Graham扫描算法的关系。“回滚”可能会被多次使用，但它只影响自上次回滚以来添加的值。 - Evgeny Kluev