yxCoding

I am a coder

Crazy Faint

yxjoey posted @ 2008年4月02日 06:24 in C语言 with tags c 程序 , 1494 阅读

号称是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。
初看此题,觉得挺好理解。如果不满足时空复杂度,这道题非常简单。这道题的关键就在于如何优化时空复杂度。
对于每个元素的最终位
置可以用如下这个公式来计算.

  1. //For an element a[i], its new place will be i>=n/2?(i-n/2)*2+1:2*i
  2. int new_pos(int i, int n){
  3.   printf("%d->%d \n", i, i>=n/2?(i-n/2)*2+1:2*i);
  4.   return i>=n/2?(i-n/2)*2+1:2*i;
  5. }

起初我的想法是循环交换,也就是A要B所在的位置去,就把B值拿出来,然后B再去找它所要的位置。如此循环,直到某个元素的新的位置是A的位置,这样循环一个圈下来可以让一部分元素到达他们的最终位置,而且空间复杂度为O(1).一个循环替换的代码如下:

  1. void reorder(int a[], int n, int cur){
  2.   int pos;
  3.   int tmp;
  4.   tmp = a[cur];
  5.   pos = new_pos(cur, n);
  6.   while(pos!=cur){
  7.     swap(&tmp, &a[pos]);
  8.     pos = new_pos(pos, n);
  9.   }
  10.   a[cur] = tmp;
  11. }

然而现在的问题是我们无法判断那些元素是已经移动过的,所以也没有办法去找新的这样的循环替换圈。就这样我想啊想啊。。怎么想也想不出方法。于是我终于忍不住了,到网上去搜,最后在阅微堂发现一个另我崩溃的结果。原来这个算法可以写成一个12页的论文。看来如果真的是Google的面试题,那它就是想测试应试者的思考能力,并没有期望有人能做出来。

有些问题看似简单,其实深不可测。12页的论文暂时没时间看了,有机会可以拜读一下。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter