如何输出B的排列，使A是一个摇摇晃晃的？
如何输出B的排列，使A是一个摇摇晃晃的？
提问于 2015-02-17 17:24:43
我所面对的问题如下：
给出了一个没有排序的实数数组
B[1 . . 2n+1]，给出了一个线性时间算法，该算法输出B的置换A[1..2n+1]，使得A是一个摆动的数组。
我基本上做了一个合并排序，并改变了它：
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)时间做这件事。
我应该使用计数排序/基排序/桶排序来获得线性时间，然后修改它以得到一个摇摇晃晃的数组吗？
回答 2
Stack Overflow用户
回答已采纳
发布于 2015-02-17 17:34:17
有一个简单的线性解：
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])正确性证明：
让我们使用归纳：
- 基大小写:只处理一个元素，不违反约束。
- 步骤:如果
i % 2 == 0：如果我们在这一步没有交换任何东西，前缀仍然有效。否则，我们会遇到以下情况：a[i - 2] >= a[i - 1] > a[i]。当我们进行交换时，我们可以看到i - 2和i - 1元素的约束没有被违反，最后的位置是固定的。对于一个奇怪的i来说，情况也是相似的。
Stack Overflow用户
发布于 2017-03-06 17:18:27
下面是上述算法的C++实现。
#include <iostream>
using namespace std;
void swap(int& a,int& b){
a=a+b;
b=a-b;
a=a-b;
}
int main() {
int*B ;
int n;
cin>>n ; n=2*n;
B=new int[n] ;
for(int i=0;i<n;i++){
cin>>B[i] ;
}
for(int i=1;i<n;i++){
if(i%2==0&&B[i]>B[i-1])
swap(B[i],B[i-1]);
else if(i%2==1&&B[i]<B[i-1])
swap(B[i],B[i-1]);
}
for(int i=0;i<n;i++){
cout<<B[i]<<" ";
}
return 0;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/28567334
复制相关文章
相似问题
腾讯云开发者
