排列一个数组,使得它们之间不存在2个数字的平均值

Question

正如问题所说,找到一个算法来排列数组.这是一个Facebook面试问题.

平均值需要准确.我们不是平均的,也不是平均的.

编辑:举一个例子,如果数字是1,2,5,9,那么排列{1,9,2,5}是有效的,但{1,5,9,2}不是平均值1和9是5并位于它们之间.

Answer 1

除非没有有趣的事情（重复条目），初步检查表明这是有效的：

    void check(ref int x, ref int y, int z)
    {
        if ((x + z) / 2 == y)
        {
            int temp = x;
            x = y;
            y = temp;
        }
    }

    int[] nums = new int[] { 1, 2, 3, 4, 5, 6, 7, 8 };

    for( int i = 0; i < nums.Count() - 3; i++)
    {
        check(ref nums[i], ref nums[i + 1], nums[i + 2]);
    }

现场为此创建一个处理所有情况（重复条目）的算法，尽管可能有点棘手。您将需要某种形式的递归函数来遍历并找到满足条件的下一个条目，但不会破坏列表。

这可能看起来微不足道，但请考虑以下情况：

  { 2,2,2,4,5,6,2,2,2,2 }

你必须循环回到开头，但仍然没有正确的答案。