一个算法题目

phy0077

输入 a1, a2, ... , an, b1, b2, ... , bn, 如何在O(n)的时间，用O(1)的空间，将这个序列顺序改为 a1, b1, ...., an, bn.

据说是google的笔试题目，大家看看

cjaizss

我的猜想错了

cjaizss

虽然任何两个排列都可以经过小于n次对换得到,
但此题限制O(1)空间复杂度,于是没有标志可以记录是否经历过对换.
有答案吗?

cjaizss

以下是生成循环的shell程序

1. 
   
2. #!/bin/bash
   
3. echo $1|awk '{x=$1;n=0;}
   
4. {
   
5.         for(i=1;i<=x*2;i+=1)
   
6.                 b[i]=1;
   
7.         for(i=1;i<=2*x;i++)
   
8.                 if(b[i] == 0)
   
9.                         continue;
   
10.                 else {
    
11.                         b[i]=0;
    
12.                         y=i;
    
13.                         s=i;
    
14.                         j=i;
    
15.                         while(1) {
    
16.                                 if(j>x)
    
17.                                         j=2*(j-x);
    
18.                                 else
    
19.                                         j=j*2-1;
    
20.                                 if(j==y)
    
21.                                         break;
    
22.                                 s=s","j;
    
23.                                 b[j]=0;
    
24.                         }
    
25.                         S[n++]="("s")";
    
26.                 }
    
27.         for(i=0;i<n;i++)
    
28.                 print S[i];
    
29. }'
    

复制代码

比如当n=256时,
该置换是以下循环的乘积,很复杂

1. 
   
2. (1)
   
3. (2,3,5,9,17,33,65,129,257)
   
4. (4,7,13,25,49,97,193,385,258)
   
5. (6,11,21,41,81,161,321,130,259)
   
6. (8,15,29,57,113,225,449,386,260)
   
7. (10,19,37,73,145,289,66,131,261)
   
8. (12,23,45,89,177,353,194,387,262)
   
9. (14,27,53,105,209,417,322,132,263)
   
10. (16,31,61,121,241,481,450,388,264)
    
11. (18,35,69,137,273,34,67,133,265)
    
12. (20,39,77,153,305,98,195,389,266)
    
13. (22,43,85,169,337,162,323,134,267)
    
14. (24,47,93,185,369,226,451,390,268)
    
15. (26,51,101,201,401,290,68,135,269)
    
16. (28,55,109,217,433,354,196,391,270)
    
17. (30,59,117,233,465,418,324,136,271)
    
18. (32,63,125,249,497,482,452,392,272)
    
19. (36,71,141,281,50,99,197,393,274)
    
20. (38,75,149,297,82,163,325,138,275)
    
21. (40,79,157,313,114,227,453,394,276)
    
22. (42,83,165,329,146,291,70,139,277)
    
23. (44,87,173,345,178,355,198,395,278)
    
24. (46,91,181,361,210,419,326,140,279)
    
25. (48,95,189,377,242,483,454,396,280)
    
26. (52,103,205,409,306,100,199,397,282)
    
27. (54,107,213,425,338,164,327,142,283)
    
28. (56,111,221,441,370,228,455,398,284)
    
29. (58,115,229,457,402,292,72,143,285)
    
30. (60,119,237,473,434,356,200,399,286)
    
31. (62,123,245,489,466,420,328,144,287)
    
32. (64,127,253,505,498,484,456,400,288)
    
33. (74,147,293)
    
34. (76,151,301,90,179,357,202,403,294)
    
35. (78,155,309,106,211,421,330,148,295)
    
36. (80,159,317,122,243,485,458,404,296)
    
37. (84,167,333,154,307,102,203,405,298)
    
38. (86,171,341,170,339,166,331,150,299)
    
39. (88,175,349,186,371,230,459,406,300)
    
40. (92,183,365,218,435,358,204,407,302)
    
41. (94,187,373,234,467,422,332,152,303)
    
42. (96,191,381,250,499,486,460,408,304)
    
43. (104,207,413,314,116,231,461,410,308)
    
44. (108,215,429,346,180,359,206,411,310)
    
45. (110,219,437,362,212,423,334,156,311)
    
46. (112,223,445,378,244,487,462,412,312)
    
47. (118,235,469,426,340,168,335,158,315)
    
48. (120,239,477,442,372,232,463,414,316)
    
49. (124,247,493,474,436,360,208,415,318)
    
50. (126,251,501,490,468,424,336,160,319)
    
51. (128,255,509,506,500,488,464,416,320)
    
52. (172,343,174,347,182,363,214,427,342)
    
53. (176,351,190,379,246,491,470,428,344)
    
54. (184,367,222,443,374,236,471,430,348)
    
55. (188,375,238,475,438,364,216,431,350)
    
56. (192,383,254,507,502,492,472,432,352)
    
57. (220,439,366)
    
58. (224,447,382,252,503,494,476,440,368)
    
59. (240,479,446,380,248,495,478,444,376)
    
60. (256,511,510,508,504,496,480,448,384)
    
61. (512)
    

复制代码

phy0077

回复 3# cjaizss


    据说有答案，这题目貌似需要很多技巧

cjaizss

那么，只能想个办法吧这个置换用几个相交的循环乘积表示

专操五毛

google "完美洗牌 算法"

xyfree

弱弱地说一句....
只要n是已知的，不是用异或就可以搞定的么？

设这个数组或者链表为s, s[1] 即 a[1]，s[2]即a[2]。。。s[n+1]即b[1]。。。s[2n] 即b[n]

从a[1]开始，依次与a[i+1]进行异或，直到 i==n-1，存储运算结果为A
从b[1]开始，直到b[n]做同样的事情,运算结果为B

然后开始循环直接改写数组或链表元素的值，

循环内部

1. 
   
2. t = s[2n];
   
3. s[2n] = B ^ s[2n];
   
4. B^=t;
   
5. t = s[2n-1];
   
6. s[2n-1] = A ^ s[2n-1]
   
7. A^=t;
   

复制代码

只需要3个额外空间：t, A, B。
就足够完成全部交换，这样算是O(1)空间吧？
时间貌似是 O(2n)，还好....


但愿是我理解错题目了....

peidright

a1, a2, ... , an, b1, b2, ... , bn,
a2 与 b1 互换

形成
a1 b1 a3 ... an  ; a2,b2,.b3,....bn
把前面的仍然看作 a, 后面的看作 b;
执行  a3  与 b1互换

得到
a1 b2 a2,a4,....an; a3,b2,......bn;


下一次，从 a4开始， 继续进行。
不知道下标 i 是不是存储？ 如果不是的话，好像可以不用额外存粗空间。好像很简单很自然的做法，是我没看明白题意？

phy0077

弱弱地说一句....
只要n是已知的，不是用异或就可以搞定的么？

设这个数组或者链表为s, s[1] 即 a[1]， ...
xyfree 发表于 2010-03-21 03:50

    空间需要O(1)