Crazy Faint
号称是Google的面试题：输入a_1, a_2, ..., a_n, b_1, b_2, ..., b_n，如何在O(n)的时间，用O(1)的空间，将这个序列顺序改为a_1, b_1, ..., a_n, b_n。
初看此题，觉得挺好理解。如果不满足时空复杂度，这道题非常简单。这道题的关键就在于如何优化时空复杂度。
对于每个元素的最终位置可以用如下这个公式来计算.
-
//For an element a[i], its new place will be i>=n/2?(i-n/2)*2+1:2*i
-
int new_pos(int i, int n){
-
return i>=n/2?(i-n/2)*2+1:2*i;
-
}
起初我的想法是循环交换，也就是A要B所在的位置去，就把B值拿出来，然后B再去找它所要的位置。如此循环，直到某个元素的新的位置是A的位置，这样循环一个圈下来可以让一部分元素到达他们的最终位置，而且空间复杂度为O(1).一个循环替换的代码如下：
-
void reorder(int a[], int n, int cur){
-
int pos;
-
int tmp;
-
tmp = a[cur];
-
pos = new_pos(cur, n);
-
while(pos!=cur){
-
swap(&tmp, &a[pos]);
-
pos = new_pos(pos, n);
-
}
-
a[cur] = tmp;
-
}
然而现在的问题是我们无法判断那些元素是已经移动过的，所以也没有办法去找新的这样的循环替换圈。就这样我想啊想啊。。怎么想也想不出方法。于是我终于忍不住了，到网上去搜，最后在阅微堂发现一个另我崩溃的结果。原来这个算法可以写成一个12页的论文。看来如果真的是Google的面试题，那它就是想测试应试者的思考能力，并没有期望有人能做出来。
有些问题看似简单，其实深不可测。12页的论文暂时没时间看了，有机会可以拜读一下。
评论 (0)
yxjoey
最新评论
最新留言
友情链接
我的豆瓣收藏
浏览计数器
62387