5

例如我们有数组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;
 }

“漂亮”算法的任何想法？:)

4

3 回答 3

2

免责声明此解决方案将安排项目以绝对值的差异增长。感谢@Will Ness

根据the difference between every pair is in ascending order需求提供一种解决方案。

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

[n/2, n/2+1, n/2-1, n/2+2, n/2-2, n/2+3 ...]如果更多元素位于第 (n/2) 个元素的右侧，则首先转到 +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 = 5th）、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

于 2013-03-31T09:16:32.780 回答
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

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

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

我们以另一个数组为例：{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 左侧的差异是正数，因此值本身是升序的，即已排序。因此，在我们选择其中一些移动到最大元素的右侧之后，剩下的任何东西都保持原样，并且（正）差异必须按降序排列。如果是，则找到解决方案。

这里没有解决方案。可能性是：

...  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，有几种解决方案是可能的。

于 2013-03-31T10:05:44.797 回答
1

这个问题的解决方案并不总是可行的。例如，数组X[] = {0, 0, 0}不能按要求“排序”，因为两个差异总是相等的。

In case this problem has a solution, array values should be "sorted" as shown on the left diagram: some subset of the values in ascending order should form prefix of the resulting array, then all the remaining values in descending order should form its suffix. And "sorted" array should be convex.

enter image description here

This gives a hint for an algorithm: sort the array, then split its values into two convex subsets, then extract one of these subsets and append it (in reverse order) at the end.

A simple (partial) implementation would be: sort the array, find a subset of values that belong to convex hull, then check all the remaining values, and if they are convex, append them at the end. This algorithm works only if one of the subsets lies completely below the other one.

If the resulting subsets intersect (as shown on the right diagram), an improved version of this algorithm may be used: split sorted array into segments where one of the subsets lies completely below other one (A-B, B-C), then for each of these segments find convex hull and check convexity of the remaining subset. Note that X axis on the right diagram corresponds to the array indexes in a special way: for subset intersections (A, B, C) X corresponds to an index in ascending-sorted array; X coordinates for values between intersections are scaled according to their positions in the resulting array.

Sketch of an algorithm

  1. Sort the array in ascending order.
  2. Starting from the largest value, try adding convex hull values to the "top" subset (in a way similar to Graham scan algorithm). Also put all the values not belonging to convex hull to the "bottom" subset and check its convexity. Continue while all the values properly fit to either "top" or "bottom" subset. When the smallest value is processed, remove one of these subsets from the array, reverse the subset, and append at the and of the array.
  3. If after adding some value to the "top" subset, the "bottom" subset is not convex anymore, rollback last addition and check if this value can be properly added to the "bottom" subset. If not, stop, because input array cannot be "sorted" as required. Otherwise, exchange "top" and "bottom" subsets and continue with step 2 (already processed values should not be moved between subsets, any attempt to move them should result in going to step 3).

In other words, we could process each value of sorted array, from largest to smallest, trying to append this value to one of two subsets in such a way that both subsets stay convex. At first, we try to place a new value to the subset where previous value was added. This may make several values, added earlier, unfit to this subset - then we check if they all fit to other subset. If they do - move them to other subset, if not - leave them in "top" subset but move current value to other subset.

Time complexity

Each value is added or removed from "top" subset at most once, also it may be added to "bottom" subset at most once. And for each operation on an element we need to inspect only two its nearest predecessors. This means worst-case time complexity of steps 2 and 3 is O(N). So overall time complexity is determined by the sorting algorithm on step 1.

于 2013-03-31T13:43:05.140 回答