一個算法題目

phy0077

輸入 a1, a2, ... , an, b1, b2, ... , bn, 如何在O(n)的時間，用O(1)的空間，將這個序列順序改為 a1, b1, ...., an, bn.

據(jù)說是google的筆試題目，大家看看

cjaizss

我的猜想錯了

cjaizss

雖然任何兩個排列都可以經(jīng)過小于n次對換得到,
但此題限制O(1)空間復(fù)雜度,于是沒有標(biāo)志可以記錄是否經(jīng)歷過對換.
有答案嗎?

cjaizss

以下是生成循環(huán)的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. }'
    

復(fù)制代碼

比如當(dāng)n=256時,
該置換是以下循環(huán)的乘積,很復(fù)雜

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)
    

復(fù)制代碼

phy0077

回復(fù) 3# cjaizss


    據(jù)說有答案，這題目貌似需要很多技巧

cjaizss

那么，只能想個辦法吧這個置換用幾個相交的循環(huán)乘積表示

專操五毛

google "完美洗牌 算法"

xyfree

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

設(shè)這個數(shù)組或者鏈表為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，存儲運算結(jié)果為A
從b[1]開始，直到b[n]做同樣的事情,運算結(jié)果為B

然后開始循環(huán)直接改寫數(shù)組或鏈表元素的值，

循環(huán)內(nèi)部

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;
   

復(fù)制代碼

只需要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;
執(zhí)行  a3  與 b1互換

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


下一次，從 a4開始， 繼續(xù)進行。
不知道下標(biāo) i 是不是存儲？ 如果不是的話，好像可以不用額外存粗空間。好像很簡單很自然的做法，是我沒看明白題意？

phy0077

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

設(shè)這個數(shù)組或者鏈表為s, s[1] 即 a[1]， ...
xyfree 發(fā)表于 2010-03-21 03:50

    空間需要O(1)