7

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

平均值需要准确。我们不取舍，取平均值的底线或天花板。

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

4

2 回答 2

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 }

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

于 2013-10-14T18:58:17.510 回答
1

被天鹰船长打败了，但是……

Module Module1

    Sub Main()
        Dim a() As Integer = {9, 4, 7, 6, 4, 4, 3, 4, 1}
        Dim n = a.Length

        'TODO: check that sanity has a reasonable vale
        Dim sanity As Integer = n
        Dim ok As Boolean = False
        Dim temp As Integer

        While Not ok And sanity > 0
            ok = True
            For i = 0 To n - 3
                If ((a(i) + a(i + 2)) / 2) = a(i + 1) Then
                    temp = a(i)
                    a(i) = a(i + 1)
                    a(i + 1) = temp
                    ok = False
                End If

            Next

            sanity -= 1
        End While
        Console.WriteLine("OK: " & ok.ToString())

        Console.WriteLine(String.Join(" ", a))

        Console.ReadLine()

    End Sub

End Module
于 2013-10-14T19:03:46.730 回答