我遇到了以下问题:
Given an unsorted array
B[1 . . 2n+1]
of real numbers, give a linear time algorithm that outputs a permutationA[1..2n+1]
ofB
such thatA
is a wiggly.
我基本上做了一个合并排序并改变了它:
MergeSort(a,n)
int i=2;
while (i ≤ n)
{
Swap(a[i−1], a[i]);
i=i+2;
}
但时间复杂度为 O(nlogn) + O(n)
(分别来自排序和循环),产生 O(nlogn)
。但我想在 O(n)
时间内完成。
我是否应该使用计数排序/基数排序/桶排序来获得线性时间,然后对其进行修改以获得一个摇摆不定的数组?
最佳答案
有一个简单的线性解决方案:
for i = 2 ... 2 * n - 1:
if i % 2 == 0 and a[i] < a[i - 1] or i % 2 == 1 and a[i] > a[i - 1]:
swap(a[i], a[i - 1])
正确性证明:
让我们使用归纳法:
基本情况:只处理一个元素,不违反任何约束。
步骤:if
i % 2 == 0
:如果我们在这一步不交换任何东西,前缀仍然有效。否则,我们会遇到以下情况:a[i - 2] >= a[i - 1] > a[i]
。当我们进行交换时,我们可以看到i - 2
和i - 1
元素没有违反约束,并且最后一个位置是固定的。对于奇数i
,情况类似。
关于arrays - 如何输出 B 的排列,使得 A 是一个摆动的?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28567334/