在 Careercup 上找到这个面试题
给定一个包含 n 个整数的数组 A。 重新排列数组使得 A[0]<=A[1]>=A[2]<=A[3]>=A[4]<=A[5] 等等
编辑:数组未排序，您必须在线性时间 O(N) 内完成
我无法在线性时间内找到解决方案，我得到的最接近的解决方案是对数组进行排序，然后重新排列元素。任何人都知道如何在线性时间内完成它？这甚至可以在线性时间内完成吗？
我提出的解决方案是在 nlogn 时间内对数组进行排序，然后将每个奇数元素 i 重新排列为 i-1 和 i+1 交替。
最佳答案
使用quickselect在 O(n) 中找到数组的中位数。这将允许您将数组分成两个相等(或几乎相等)的部分:小于或等于中位数 (A) 最多 n/2 个元素的部分，其余部分 (B)，即定义，大于或等于中位数。
使用这两部分排列数组，如下所示:
A B A B A B A
这是正确的，因为根据定义，每个项目 A 都将小于或等于每个 B。
关于arrays - 按特定顺序排列数组中的元素，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35213109/