我做的google數(shù)組隨機(jī)排序的算法
我做的google數(shù)組隨機(jī)排序的算法
發(fā)信人: northor(追求理想的過(guò)程是曲折艱辛的!), 信區(qū): Job
標(biāo) 題: 我做的google數(shù)組隨機(jī)排序的算法
發(fā)信站: 瀚海星云 (2006年05月30日23:44:13 星期二), 站內(nèi)信件 WWWPOST
由于一開(kāi)始覺(jué)得這個(gè)題目不太好做,
就放在最后做了,
結(jié)果時(shí)間不夠,只寫(xiě)了算法:
我考慮題干強(qiáng)調(diào)的是一定要隨機(jī),就是越亂越好,
于是我就聯(lián)想到了一堆乒乓球在籠子里搖啊搖的,抽獎(jiǎng)的過(guò)程,
這個(gè)過(guò)程應(yīng)該算是符合題目的要求吧,
那么怎么用random函數(shù)來(lái)實(shí)現(xiàn)這個(gè)功能呢?
我又建立了三個(gè)int型數(shù)組,b[len],c[len],d[len]
首先N = len,乒乓球的個(gè)數(shù)是N,
然后搖獎(jiǎng):利用random產(chǎn)生0到N-1的隨機(jī)數(shù),
記作b[0],d[0]=b[0];
這是搖出的第一個(gè)球的號(hào)碼,然后對(duì)c[len]賦值,
這個(gè)數(shù)組,我規(guī)定它的作用是對(duì)剩下的乒乓球標(biāo)記,
因?yàn)閾u出了一個(gè)球,剩下了N-1個(gè)，
而隨機(jī)數(shù)只能在0開(kāi)始的連續(xù)整數(shù)之間產(chǎn)生，
所以剩下的球的號(hào)碼要是連續(xù)整數(shù)就可以繼續(xù)搖了，
所以c[len]記錄我對(duì)乒乓球的重新標(biāo)號(hào)，
如果最初乒乓球的號(hào)碼小于b[0],就保持原來(lái)的號(hào)碼，
等于b[0],就讓號(hào)碼為N(作廢），
大于b[0]的,全部減1，
這樣剩下的N－1個(gè)乒乓球的`標(biāo)號(hào)就是0到N－2了，
然后產(chǎn)生利用random產(chǎn)生0到N-2的隨機(jī)數(shù)，
對(duì)標(biāo)記號(hào)碼搖獎(jiǎng)，利用搖出的乒乓球的標(biāo)記號(hào)碼b[1]，
查到它的真實(shí)號(hào)碼d[1]，
這樣第二個(gè)隨機(jī)位置d[1]就產(chǎn)生了，
然后再根據(jù)b[1]給剩下的N－2個(gè)乒乓球重新標(biāo)記，
如果乒乓球的標(biāo)記號(hào)碼小于b[1],就保持原來(lái)的標(biāo)記號(hào)碼，
等于b[1]，就讓號(hào)碼為N(作廢），
大于b[1]不等于N的,全部減1，
大于b[1]等于N的,不變。
重新標(biāo)記之后，產(chǎn)生0到N-3的隨機(jī)數(shù)，
就產(chǎn)生了第三個(gè)乒乓球的隨機(jī)號(hào)碼b[2]，
反回去查詢真實(shí)號(hào)碼，得到d[2];
......
最后我們得到了d[len]這個(gè)數(shù)組，
可以讓c[i]=a[d[i]];
然后再把c賦給a，
這樣一個(gè)模擬乒乓球搖獎(jiǎng)的隨機(jī)過(guò)程就完成了，
如果有可能，可以看到a[len]
打亂后排列的順序，
和一個(gè)一個(gè)地?fù)u出乒乓球號(hào)碼的概率分布是一致的。
期待高手點(diǎn)評(píng)，^_^.
【我做的google數(shù)組隨機(jī)排序的算法】相關(guān)文章：
2017年Google的面試流程09-17
職場(chǎng)人做職場(chǎng)充電的原因08-01
現(xiàn)在零元的做代理掙錢(qián)的生意10-23
腦積水的預(yù)防工作怎么做10-12
認(rèn)識(shí)自己做職場(chǎng)上的蘭博08-11
如何做最好的創(chuàng)新勵(lì)志創(chuàng)業(yè)12-09
求職故事：做自己感興趣的工作07-12