algorithm - 2 つの数値の平均がそれらの間に位置しないように配列を配置する

Question

質問が言うように、配列を配置するアルゴリズムを見つけます。これはFacebookのインタビューの質問でした.

平均は正確である必要があります。丸めたり、平均の下限や上限を取ったりしません。

編集：例を引用すると、数字が1,2,5,9の場合、配置{1,9,2,5}は有効ですが、{1,5,9,2}は1の平均と9 は 5 で、その間にあります。

Answer 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