- 相關推薦
我做的google數組隨機排序的算法
我做的google數組隨機排序的算法
發信人: northor(追求理想的過程是曲折艱辛的!), 信區: Job
標 題: 我做的google數組隨機排序的算法
發信站: 瀚海星云 (2006年05月30日23:44:13 星期二), 站內信件 WWWPOST
由于一開始覺得這個題目不太好做,
就放在最后做了,
結果時間不夠,只寫了算法:
我考慮題干強調的是一定要隨機,就是越亂越好,
于是我就聯想到了一堆乒乓球在籠子里搖啊搖的,抽獎的過程,
這個過程應該算是符合題目的要求吧,
那么怎么用random函數來實現這個功能呢?
我又建立了三個int型數組,b[len],c[len],d[len]
首先N = len,乒乓球的個數是N,
然后搖獎:利用random產生0到N-1的隨機數,
記作b[0],d[0]=b[0];
這是搖出的第一個球的號碼,然后對c[len]賦值,
這個數組,我規定它的作用是對剩下的乒乓球標記,
因為搖出了一個球,剩下了N-1個，
而隨機數只能在0開始的連續整數之間產生，
所以剩下的球的號碼要是連續整數就可以繼續搖了，
所以c[len]記錄我對乒乓球的重新標號，
如果最初乒乓球的號碼小于b[0],就保持原來的號碼，
等于b[0],就讓號碼為N(作廢），
大于b[0]的,全部減1，
這樣剩下的N－1個乒乓球的標號就是0到N－2了，
然后產生利用random產生0到N-2的隨機數，
對標記號碼搖獎，利用搖出的乒乓球的標記號碼b[1]，
查到它的真實號碼d[1]，
這樣第二個隨機位置d[1]就產生了，
然后再根據b[1]給剩下的N－2個乒乓球重新標記，
如果乒乓球的標記號碼小于b[1],就保持原來的標記號碼，
等于b[1]，就讓號碼為N(作廢），
大于b[1]不等于N的,全部減1，
大于b[1]等于N的,不變。
重新標記之后，產生0到N-3的隨機數，
就產生了第三個乒乓球的隨機號碼b[2]，
反回去查詢真實號碼，得到d[2];
......
最后我們得到了d[len]這個數組，
可以讓c[i]=a[d[i]];
然后再把c賦給a，
這樣一個模擬乒乓球搖獎的隨機過程就完成了，
如果有可能，可以看到a[len]
打亂后排列的順序，
和一個一個地搖出乒乓球號碼的概率分布是一致的。
期待高手點評，^_^.
【我做的google數組隨機排序的算法】相關文章：
google公司的招聘題目02-16
google的招聘怪題02-18
google招聘筆試題02-18
Google筆試題目分享11-21
Google公司預選筆試試題02-18
Google面試官談面試技巧02-18
剛剛完成了Google的電話面試11-19
google一面面試面經分享！02-24