前端面試(演算法篇) - 數組亂序

一、面試題

問：有一個長度為 100 的數組，如何從中隨機挑選 50 個元素，組成一個新的數組？

答：這個...那個...emmmmmm

問：那先不挑 50 個，就挑一個數，知道怎麼做嗎？

答：這個我知道！隨機生成一個 0 ~ 99 的數，然後去原數組取對應位置的元素就可以了～

let randomIndex = arr[Math.floor(Math.random() * arr.length)];

問：好，回到最初的問題，怎麼挑選 50 個元素？

答：我知道了，在 0 ～ 99 的範圍內，隨機生成 50 個不重覆的數字！

問：是這個思路，具體的實現呢？記得保證效率哦。

答：（吧啦吧啦吧啦）

問：現在假設數組的元素都是 String 類型，如果要把這個數組元素的順序打亂，有什麼辦法麽？

答：數組的 sort() 方法可以傳入一個函數作為參數，這個函數的返回值可以決定排列順序。在這個函數中寫一個隨機數，然後就能亂序了。

問：這是一個思路，但這隻是偽隨機。

答：啊咧？

問：聽說過“洗牌演算法”嗎？

二、隨機取數

按照上面隨機挑選一個數的思路，從原數組中隨機抽取一個數，然後使用 splice 刪掉該元素

function getRandomArrElement(arr, count) {
    let res = []
    while (res.length < count) {
        // 生成隨機 index
        let randomIdx = (Math.random() * arr.length) >> 0;
        // splice 返回的是一個數組
        res.push(arr.splice(randomIdx, 1)[0]);
    }
    return res
}

上面生成隨機 index 用到了按位右移操作符 >> 

當後面的操作數是 0 的時候，該語句的結果就和 Math.floor() 一樣，是向下取整

但位操作符是在數值表示的最底層執行操作，因此速度更快

// 按位右移
(Math.random() * 100) >> 0

// Math.floor
Math.floor(Math.random() * 100)

/* 這兩種寫法的結果是一樣的，但位操作的效率更高 */

三、通過 sort 亂序

首先認識一下 Array.prototype.sort()

這個方法可以傳入一個參數 compareFunction，這個參數必須是函數

同時 sort() 會暴露出 Array 中的兩個元素 (a, b) 作為參數傳給 compareFunction

sort() 會根據 compareFunction(a, b) 的返回值，來決定 a 和 b 的相對位置：

• 如果 compareFunction(a, b) 小於 0 ，那麼 a 會被排列到 b 之前；
• 如果 compareFunction(a, b) 大於 0 ，那麼 b 會被排列到 a 之前；
• 如果 compareFunction(a, b) 等於 0 ， a 和 b 的相對位置不變（不穩定！）

根據以上規則，可以在 compareFunction 中生成一個隨機數，然後根據隨機數做運算，返回一個正負未知的 Number，從而實現亂序

function randomSort(a,b) { 
    return .5 - Math.random(); 
}

let arr = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'];
arr.sort(randomSort);

但這並不是真正的亂序，電腦的 random 函數因為迴圈周期的存在，無法生成真正的隨機數

四、Fisher–Yates shuffle 洗牌演算法

洗牌演算法的思路是：

先從數組末尾開始，選取最後一個元素，與數組中隨機一個位置的元素交換位置

然後在已經排好的最後一個元素以外的位置中，隨機產生一個位置，讓該位置元素與倒數第二個元素進行交換

以此類推，打亂整個數組的順序

function shuffle(arr) {
  let len = arr.length;

  while (len) {
    let i = (Math.random() * len--) >> 0;
    // 交換位置
    let temp = arr[len];
    arr[len] = arr[i];
    arr[i] = temp;
  }

  return arr;
}

再結合 ES6 的解構賦值，使用洗牌演算法就更方便了：

Array.prototype.shuffle = function() {
    let m = this.length, i;
    while (m) {
        i = (Math.random() * m--) >>> 0;
        [this[m], this[i]] = [this[i], this[m]]
    }
    return this;
}

五、用洗牌演算法隨機取數

再回到從長度為 100 的數組中取 50 個數的問題

之前用的是 splice 修改原數組，如果結合洗牌演算法，又會有別的思路

最好是自己先思考一下，然後再展開代碼進行比較

function getRandomArrElement(arr, count) {
    let shuffled = arr.slice(0), 
        i = arr.length, 
        min = i - count, 
        temp, 
        index;
    while (i > min) {
        index = Math.floor((i--) * Math.random());
        temp = shuffled[index];
        shuffled[index] = shuffled[i];
        shuffled[i] = temp;
    }
    return shuffled.slice(min);
}

最後放個彩蛋，關於兩種隨機取數的性能孰優孰劣

我用 Array.form 生成了一個長度為一百萬的數組，然後從中隨機取十萬個數

首先是使用 splice 的方案：

 然後是洗牌演算法：

喵喵喵？！！ 

參考資料：

《js隨機數組，js隨機洗牌演算法》

《也談前端面試常見問題之『數組亂序』》

《How to randomize (shuffle) a JavaScript array?》