一道google的面试题（转自瀚海星云）

jiakuant 2007-12-28 04:39:15

加精

输入a_1, a_2, ..., a_n, b_1, b_2, ..., b_n，如何在O(n)的时间，用O(1)的空间，
将这个序列顺序改为a_1, b_1, ..., a_n, b_n。

这个问题在瀚海星云上跟出了好几十的跟帖，看看大家有没有什么好的解法！！！

...全文

10004 229 打赏收藏转发到动态举报

写回复

用AI写文章

229 条回复

切换为时间正序

请发表友善的回复…

发表回复

wwwypy 2008-10-10

打赏
举报

好好看看数据结构上面的题不难做出来！

zsxcn 2008-10-08

打赏
举报

mark

xiaofengsheng 2008-10-08

打赏
举报

[Quote=引用 218 楼 lytxyz 的回复:]
1. X指向a_2，Y指向b_1
2. 交换X与Y指向的两个元素
3. X向后移一个元素
4. X是否与Y指向同一个元素？若是结束，否则继续
5. 交换X与Y指向的两个元素
6. X向后移一个元素，Y向后移一个元素
7. 转到第 2 步
[/Quote]
支持！

xiaofengsheng 2008-10-08

打赏
举报

Norse 2008-10-05

打赏
举报

按这个迭代递推公式似乎是：T(n) = T(n-1)*2，显然不是O(n)
[Quote=引用 44 楼 euroman 的回复:]
用迭代
a1 a2 a3 ... an | b1 b2 b3 ... bn
a1 b1 a3 ... an | a2 b2 b3 ... bn
...
a1 b1 a3 b3 a5 b5 ... a(2k-1) b(2k-1) | a2 b2 a4 b4 ... a(2n) b(2n)

以这个为一次迭代

那么每次迭代就把数组分成两个小的同类型的问题可以得出第推关系
T(n) = T(n/2) + n

根据算法理论第推关系公式
T(n) = a * T(n/c) + b*n

这里a = 1， c = 2

那么我们有T(n) = T(n/2) + n

由于T(n) = b*n*sum( pow…
[/Quote]

Norse 2008-10-05

打赏
举报

这个第一次迭代只是初始化

Norse 2008-10-05

打赏
举报

也不难，但想来想去都想不出只用一个循环的方法
但可以有多重循环但形如(1/2+1/4...+1/logn)*n的方法，这个数列是收敛的，所以虽然多重循环但依然满足O(n)

crazylightning 2008-10-05

打赏
举报

编程论坛 10334876
群 10334876 (黑客帝国)期待你的加入...
欢迎编程老手一起研讨软件开发中的难点,疑点以及各种稀奇古怪的代码...

本IT论坛仅限于研讨软件相关知识，开发语言、工具不限
(C/C++,C#.net,Java,python,PHP,SQl,xml,AS,JS等）...

sdfiyuejin 2008-10-03

打赏
举报

貌似我逃避问题了
不过,我觉得输入的时候就排好不是更省事吗...

sdfiyuejin 2008-10-03

打赏
举报

是长为2n的数组...

sdfiyuejin 2008-10-03

打赏
举报

2n数组
1 3 5 7 ...
2 4 6 8 ...

lytxyz 2008-10-02

打赏
举报

1. X指向a_2，Y指向b_1
2. 交换X与Y指向的两个元素
3. X向后移一个元素
4. X是否与Y指向同一个元素？若是结束，否则继续
5. 交换X与Y指向的两个元素
6. X向后移一个元素，Y向后移一个元素
7. 转到第 2 步

三翔馆主 2008-10-02

打赏
举报

mark

superxiaomm 2008-09-24

打赏
举报

#include "stdafx.h"
#include "string.h"
#include <string>
#include <iostream>

//std::string Array[12] = {"a1","a2","a3","a4","a5","a6","b1","b2","b3","b4","b5","b6"};
//int length = 12;
//std::string Array[10] = {"a1","a2","a3","a4","a5","b1","b2","b3","b4","b5"};
//int length = 10;
//std::string Array[8] = {"a1","a2","a3","a4","b1","b2","b3","b4"};
//int length = 8;
//std::string Array[6] = {"a1","a2","a3","b1","b2","b3"};
//int length = 6;
//std::string Array[4] = {"a1","a2","b1","b2"};
//int length = 4;
bool odd;

void swap( std::string & a, std::string & b)
{
std::string tmp = "";
tmp = a;
a = b;
b = tmp;
}

int main(int argc, char* argv[])
{
odd = (length / 2) % 2 ? 1 : 0;
int stop = length / 2;
for( int i = 1; i< stop; i=i+2)
{
swap( Array[i],Array[i+stop-1] );
}
int t = 2;

for( ;; t=t+2)
{
if(odd)
{
if( t>= stop -1)
break;
}
else
{
if( t >= 2* (stop - 1))
break;
}
swap( Array[t], Array[stop]);
swap( Array[t+1], Array[stop+1]);
}
if(odd)
{
swap(Array[stop-1],Array[2*(stop-1)]);
for( int j = stop-1; j< 2*(stop-1) - 1; j++)
{
swap( Array[j],Array[j+1]);
}
}

for( int z=0;z<length;z++)
std::cout<< Array[z]<<",";
return 0;
}
测试通过,关键就是区分n的奇偶

lisa9356 2008-09-21

打赏
举报

mark

shiyizhe 2008-09-19

打赏
举报

先对数组a和b内部排序。a1,a2,a3,a4,a5,a6;b1,b2,b3,b4,b5,b6;第一轮结束后变为a1,a4,a2,a5,a3,a6;b1,b4,b2,b5,b3,b6;然后再整合。
a1,a2,a3,a4,a5,a6,a7;b1,b2,b3,b4,b5,b6,b7;第一轮后a1,a5,a2,a6,a3,a7,a4;b4,b1,b5,b2,b6,b3,b7;然后整合。

shiyizhe 2008-09-18