?閱讀本文前纯路，請(qǐng)您先點(diǎn)擊上面的藍(lán)色字體“Android掃地僧”掩幢，“關(guān)注”后再點(diǎn)擊星標(biāo)逊拍，及時(shí)上車，優(yōu)質(zhì)干貨际邻，重磅資源第一時(shí)間送達(dá)芯丧。

首先，出一個(gè)簡(jiǎn)單的題目：有一個(gè)大小為100的數(shù)組世曾，里面的元素是從 1 到 100缨恒，怎樣隨機(jī)從里面選擇 1 個(gè)數(shù)呢？

很簡(jiǎn)單，利用 Math.random() * 100 骗露，就可以拿到一個(gè) 0 到 99 的隨機(jī)數(shù)岭佳，然后去數(shù)組找對(duì)應(yīng)的位置就行了。

下面難度提高一點(diǎn)哈萧锉！ 有一個(gè)大小為100的數(shù)組珊随，里面的元素是從 1 到 100，怎樣隨機(jī)從里面選擇 50 個(gè)數(shù)呢柿隙？注意玫恳！不能重復(fù)。

如果根據(jù)上面的思路优俘，你一定想到了：是不是隨機(jī) 50 次就行了京办？

那么問(wèn)題來(lái)了，這 50 次你是不能保證都是不能重復(fù)的帆焕，對(duì)吧惭婿！

嗯，你是不是又有靈感了叶雹，弄一個(gè)數(shù)組财饥，把每一次隨機(jī)的數(shù)都放到數(shù)組里，下一次隨機(jī)就看這個(gè)數(shù)組里面有沒(méi)有這數(shù)折晦，有的話就繼續(xù)隨機(jī)钥星，直到這個(gè)數(shù)組里面有 50 個(gè)數(shù)字就停止。完美满着！

嗯谦炒，講道理的話，這樣做也沒(méi)有問(wèn)題风喇，肯定可以實(shí)現(xiàn)題目要求宁改。但是如果我們想一下，就會(huì)發(fā)現(xiàn)問(wèn)題：如果我們考慮極限魂莫，就比如拿 99 個(gè)數(shù)字（你不要跟我說(shuō)：那就考慮相反的情況还蹲，拿 1 個(gè)數(shù)字，把這個(gè)數(shù)字去掉就行>耙考。< ）谜喊，是不是越往后重復(fù)的概率越高，那么需要重復(fù)隨機(jī)的次數(shù)也越大倦始？

是的斗遏，小老弟，你很聰明楣号，一下子就理解了最易。我們可以看下代碼：

var idxArr = []while(idxArr.length < 99){
    let idx = parseInt(Math.random()*100)
    var time = 0
    while(idxArr.includes(idx)) {
        idx = parseInt(Math.random()*100)
        console.log('time', time++)
    }
    idxArr.push(idx);}

代碼很簡(jiǎn)單怒坯，如果隨機(jī)的數(shù)字不在數(shù)組里面炫狱，就 push 進(jìn)去藻懒，否則就重新隨機(jī)。這里用了一個(gè) times 來(lái)計(jì)算每一個(gè)數(shù)需要隨機(jī)的次數(shù)视译℃揖＃可以看下輸出：

image

image

可以看到，一開始基本是沒(méi)有重復(fù)的酷含，但是到了后面最后一個(gè)鄙早，要拿到一個(gè)沒(méi)有出現(xiàn)過(guò)的隨機(jī)數(shù)需要多達(dá) 65 次。

如果你把數(shù)組再放大一點(diǎn)椅亚，結(jié)果會(huì)更加夸張限番。當(dāng)然，現(xiàn)實(shí)里不會(huì)有這么極端的情況呀舔，就像你說(shuō)的弥虐，要拿 99 個(gè)數(shù)就反過(guò)來(lái)剔除 1 個(gè)數(shù)就行了。但是呢媚赖，就算沒(méi)有 99 也可能有 50 對(duì)吧霜瘪，這個(gè)性質(zhì)還是一樣的，就是可能重復(fù)較多惧磺。

這個(gè)時(shí)候就需要換一個(gè)思路颖对，如果先將數(shù)組里面的元素打亂，那么按順序選擇前 50 個(gè)不就可以了磨隘？

是的缤底！

但我們得注意什么叫亂？

一副撲克有 54 張牌番捂，有 54! 種排列方式训堆。所謂的打亂指的是，你所執(zhí)行的操作白嘁，應(yīng)該能夠 等概率地生成 這 54! 種結(jié)果中的一種坑鱼。

所以呢，進(jìn)入主題了：洗牌算法絮缅。

原理很簡(jiǎn)單：最后一個(gè)數(shù)和前面任意 n-1 個(gè)數(shù)中的一個(gè)交換鲁沥，然后倒數(shù)第二個(gè)數(shù)和前面任意 n-2 個(gè)數(shù)中的一個(gè)交換。耕魄。画恰。依次下去就行了。

洗牌算法

直接看代碼：

public void shuffle(int[] array) {
    int length = array.length;
    Random random = new Random();
    int temp;
    while (length > 0) {
        int index = random.nextInt(length);
        temp = array[index];
        array[index] = array[length -1];
        array[length -1] = temp;
        length--;
    }
}
?
//[1,2,3,4,5,6,7,8,9]
//輸出[6 1 7 8 5 2 4 9 3 ]

在整個(gè)過(guò)程中吸奴，這個(gè)算法保證了每一個(gè)元素出現(xiàn)在每一個(gè)位置的概率是相等的允扇。

這個(gè)算法真的很牛逼很經(jīng)典缠局，而且代碼很少。

需要更多算法相關(guān)考润，請(qǐng)?jiān)诠娞?hào)回復(fù)【算法】狭园，即可獲取LeetCode算法刷題精講

image

****推****薦****閱****讀****

**1. **Android進(jìn)階資源分享（2月15日更新） ****

2.Android面試題附答案，會(huì)了起碼30K****

3. 2020年今日頭條Android面試題附答案**

image

image

點(diǎn)“在看”的都漲工資了

image