按特定顺序排列数组中的元素

Question

在Careercup网站上发现了这道面试题：

给定一个有n个整数的数组A。重新排列数组，使得

A[0]<=A[1]>=A[2]<=A[3]>=A[4]<=A[5]，以此类推。

编辑：数组未排序，您需要在O（N）的线性时间内完成它。

我无法在线性时间内找到解决方案，最接近的是对数组进行排序然后重新排列元素。 有人能想到如何在线性时间内完成吗？甚至可以在线性时间内完成吗？

我的建议是在nlogn时间内对数组进行排序，然后交替重新排列每个奇数元素i、i-1和i+1。

- Ambidextrous

---

请添加您想出的解决方案。 - ChiefTwoPencils

你不需要对它进行排序。那些不等式不能是可结合的。你只需要满足最近邻居的条件。 - e0k

@StarsAreBack：请检查我的更新答案。 - Luca Angeletti

@appzYourLife 抱歉耽搁了。我已经留言了，请查看。 - Ambidextrous

Answer 1

使用quickselect在O(n)时间内找到数组的中位数。这将使您能够将数组分成两个相等（或几乎相等）的部分：小于或等于中位数（A）的n/2个元素，以及其余的（B），根据定义，大于或等于中位数。

使用这两个部分来排列数组，如下所示：

A B A B A B A

这将是正确的，因为根据定义，每个项目A都小于或等于每个B。

- Juan Lopes

---

你能否详细描述一下这个问题？我第一次使用快速选择后感到有些迷惑，我们需要为所有元素重复执行吗？ - Ambidextrous

@JuanLopez：你确定QuickSelect算法总是可以在O(n)的时间复杂度内完成吗？维基百科上确实说在最坏情况下它的时间复杂度是O(n^2)。 - Luca Angeletti

@appzYourLife 快速选择算法配合中位数的中位数算法总是O(n)时间复杂度：https://en.wikipedia.org/wiki/Median_of_medians - Juan Lopes

https://github.com/anish198519851985/Hacking/blob/master/arrange_specific_order.py 的功能与描述一致。 - newbie_old

Answer 2

您可以使用此函数（代码使用Swift编写）以波浪形的形式在时间O(n)内排列数组。

func wave(inout list: [Int]) {
    let evenIndexes = (0..<list.count).filter { $0 % 2 == 0 }

    for index in evenIndexes {
        if index > 0 && list[index] > list[index-1] {
            swap(&list[index], &list[index-1])
        }

        if index < list.count - 1 && list[index] > list[index+1] {
            swap(&list[index], &list[index+1])
        }
    }
}

这个解决方案基于这里描述的算法。

测试

var test0 = [1,2,3,4,5,6]
wave(&test0)
print(test0) // [1, 3, 2, 5, 4, 6]

var test1 = [4, 6, 2, 1, 3, 7]
wave(&test1)
print(test1) // [4, 6, 1, 3, 2, 7]

var test2 = [20, 9, 4, 2, 0]
wave(&test2)
print(test2) // [9, 20, 2, 4, 0]

时间复杂度

该函数有一个for循环，执行n/2次（仅适用于偶数索引）。因此，for循环的时间复杂度为O(n)。

在for循环内部，我们发现了一对if then语句，两者都在常量时间内执行，因此是O(1)。

因此，时间复杂度为O(n) * O(1) = O(n)，其中n是输入数组中的元素数量。

- Luca Angeletti

---

你能检查一下未排序数组的输出吗？我认为它对于未排序的数组将不起作用。例如：4、6、2、1、3、7。 - Ambidextrous

使用您输入的 [4, 6, 2, 1, 3, 7]，输出结果为 [6, 2, 4, 1, 7, 3]。 - Luca Angeletti

但是这里数字6不能放在第一位，因为它比第二个元素2要大。 - Ambidextrous

@StarksAreBack：已更新，现在应该是正确的。 我只是将两个“IF”语句中的“<”更改为此“>”。 如果您希望我尝试其他输入，请告诉我。 - Luca Angeletti

@StarksAreBack：等等，这个输入 20, 9, 4, 2, 0 的输出应该是什么？ - Luca Angeletti

Answer 3

使用NthElement算法的O(n)解决方案的C#实现：

public void WaveSortTest(int[] a)
{
    var nthElement = NthElement(a, a.Length / 2);
    var element = a[nthElement];

    var odd = 1;
    var even = 0;
    var r = new int[a.Length];
    for (int i = 0; i < a.Length; i++)
    {
        if (a[i] <= element)
        {
            r[even] = a[i];
            even += 2;
        }
        else
        {
            r[odd] = a[i];
            odd += 2;
        }
    }

    PrintArray(r);
}

private static readonly Random _rnd = new Random((int)DateTime.Today.ToFileTimeUtc());

private static int NthElement(int[] arr, int k)
{
    return NthElement(arr, 0, arr.Length, k);
}

private static int NthElement(int[] arr, int low, int high, int k)
{
    var pos = low + _rnd.Next(high - low);
    Swap(arr, pos, high - 1);

    var i = Partition(arr, low, high);

    if (k < i)
    {
        return NthElement(arr, low, i, k);
    }
    if (k > i)
    {
        return NthElement(arr, i + 1, high, k);
    }
    return i;
}

private static int Partition(int[] arr, int low, int high)
{
    var i = low - 1;
    for (var j = low; j < high; j++)
    {
        if (arr[j] <= arr[high - 1])
        {
            i++;
            Swap(arr, i, j);
        }
    }
    return i;
}

private static void Swap<T>(T[] a, int first, int second)
{
    var t = a[first];
    a[first] = a[second];
    a[second] = t;
}

private static void PrintArray(IEnumerable<int> arr)
{
    foreach (var item in arr)
    {
        Console.Write(item + " ");
    }
    Console.WriteLine();
}

- Alexander Efremov