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

Question

在 Careercup 上找到这个面试题

给定一个包含 n 个整数的数组 A。重新排列数组使得A[0]<=A[1]>=A[2]<=A[3]>=A[4]<=A[5] 等等

编辑:数组未排序，您必须在线性时间 O(N) 内完成

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

我提出的解决方案是在 nlogn 时间内对数组进行排序，然后将每个奇数元素 i 重新排列为 i-1 和 i+1 交替。

Answer 1

使用quickselect在 O(n) 中找到数组的中位数。这将允许您将数组分成两个相等(或几乎相等)的部分:小于或等于中位数 (A) 最多 n/2 个元素的部分，其余部分 (B)，即定义，大于或等于中位数。

使用这两部分排列数组，如下所示:

A B A B A B A

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