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

tracy 發布于2019-08-19 18:42 / 612人閱讀

摘要：看完部分的源碼，首先迫不及待想跟大家分享的正是本文主題數組亂序。這是一道經典的前端面試題，給你一個數組，將其打亂，返回新的數組，即為數組亂序，也稱為洗牌問題。關于數組亂序，正確的解法應該是，復雜度。

前言

終于可以開始 Collection Functions 部分了。

可能有的童鞋是第一次看樓主的系列文章，這里再做下簡單的介紹。樓主在閱讀 underscore.js 源碼的時候，學到了很多，同時覺得有些知識點可以獨立出來，寫成文章與大家分享，而本文正是其中之一（完整的系列請猛戳 https://github.com/hanzichi/underscore-analysis）。之前樓主已經和大家分享了 Object 和 Array 的擴展方法中一些有意思的知識點，今天開始解讀 Collection 部分。

看完 Collection Functions 部分的源碼，首先迫不及待想跟大家分享的正是本文主題 —— 數組亂序。這是一道經典的前端面試題，給你一個數組，將其打亂，返回新的數組，即為數組亂序，也稱為洗牌問題。

一個好的方案需要具備兩個條件，一是正確性，毋庸置疑，這是必須的，二是高效性，在確保正確的前提下，如何將復雜度降到最小，是我們需要思考的。

splice

幾年前樓主還真碰到過洗牌問題，還真的是 "洗牌"。當時是用 cocos2d-js（那時還叫 cocos2d-html5）做牌類游戲，發牌前毫無疑問需要洗牌。

當時我是這樣做的。每次 random 一個下標，看看這個元素有沒有被選過，如果被選過了，繼續 random，如果沒有，將其標記，然后存入返回數組，直到所有元素都被標記了。后來經同事指導，每次選中后，可以直接從數組中刪除，無需標記了，于是得到下面的代碼。

function shuffle(a) {
  var b = [];

  while (a.length) {
    var index = ~~(Math.random() * a.length);
    b.push(a[index]);
    a.splice(index, 1);
  }

  return b;
}

這個解法的正確性應該是沒有問題的（有興趣的可以自己去證明下）。我們假設數組的元素為 0 - 10，對其亂序 N 次，那么每個位置上的結果加起來的平均值理論上應該接近 (0 + 10) / 2 = 5，且 N 越大，越接近 5。為了能有個直觀的視覺感受，我們假設亂序 1w 次，并且將結果做成了圖表，猛戳 http://hanzichi.github.io/test-case/shuffle/splice/ 查看，結果還是很樂觀的。

驗證了正確性，還要關心一下它的復雜度。由于程序中用了 splice，如果把 splice 的復雜度看成是 O(n)，那么整個程序的復雜度是 O(n^2)。

Math.random()

另一個為人津津樂道的方法是 "巧妙應用" JavaScript 中的 Math.random() 函數。

function shuffle(a) {
  return a.concat().sort(function(a, b) {
    return Math.random() - 0.5;
  });
}

同樣是 [0, 1, 2 ... 10] 作為初始值，同樣跑了 1w 組 case，結果請猛戳 http://hanzichi.github.io/test-case/shuffle/Math.random/。

看平均值的圖表，很明顯可以看到曲線浮動，而且多次刷新，折現的大致走向一致，平均值更是在 5 上下 0.4 的區間浮動。如果我們將 [0, 1, 2 .. 9] 作為初始數組，可以看到更加明顯不符預期的結果（有興趣的可以自己去試下）。究其原因，要追究 JavaScript 引擎對于 Math.random() 的實現原理，這里就不展開了（其實是我也不知道）。因為 ECMAScript 并沒有規定 JavaScript 引擎對于 Math.random() 應該實現的方式，所以我猜想不同瀏覽器經過這樣的亂序后，結果也不一樣。

什么時候可以用這種方法亂序呢？"非正式" 場合，一些手寫 DEMO 需要亂序的場合，這不失為一種 clever solution。

但是這種解法不但不正確，而且 sort 的復雜度，平均下來應該是 O(nlogn)，跟我們接下來要說的正解還是有不少差距的。

Fisher–Yates Shuffle

關于數組亂序，正確的解法應該是 Fisher–Yates Shuffle，復雜度 O(n)。

其實它的思想非常的簡單，遍歷數組元素，將其與之前的任意元素交換。因為遍歷有從前向后和從后往前兩種方式，所以該算法大致也有兩個版本的實現。

從后往前的版本：

function shuffle(array) {
  var _array = array.concat();

  for (var i = _array.length; i--; ) {
    var j = Math.floor(Math.random() * (i + 1));
    var temp = _array[i];
    _array[i] = _array[j];
    _array[j] = temp;
  }
  
  return _array;
}

underscore 中采用從前往后遍歷元素的方式，實現如下：

// Shuffle a collection, using the modern version of the
// [Fisher-Yates shuffle](http://en.wikipedia.org/wiki/Fisher–Yates_shuffle).
_.shuffle = function(obj) {
  var set = isArrayLike(obj) ? obj : _.values(obj);
  var length = set.length;
  var shuffled = Array(length);
  for (var index = 0, rand; index < length; index++) {
    rand = _.random(0, index);
    if (rand !== index) shuffled[index] = shuffled[rand];
    shuffled[rand] = set[index];
  }
  return shuffled;
};

將其解耦分離出來，如下：

function shuffle(a) {
  var length = a.length;
  var shuffled = Array(length);

  for (var index = 0, rand; index < length; index++) {
    rand = ~~(Math.random() * (index + 1));
    if (rand !== index) 
      shuffled[index] = shuffled[rand];
    shuffled[rand] = a[index];
  }

  return shuffled;
}

跟前面一樣，做了下數據圖表，猛戳 http://hanzichi.github.io/test-case/shuffle/Fisher-Yates/。

關于證明，引用自月影老師的文章：

隨機性的數學歸納法證明

對 n 個數進行隨機：

首先我們考慮 n = 2 的情況，根據算法，顯然有 1/2 的概率兩個數交換，有 1/2 的概率兩個數不交換，因此對 n = 2 的情況，元素出現在每個位置的概率都是 1/2，滿足隨機性要求。

假設有 i 個數， i >= 2 時，算法隨機性符合要求，即每個數出現在 i 個位置上每個位置的概率都是 1/i。

對于 i + 1 個數，按照我們的算法，在第一次循環時，每個數都有 1/(i+1) 的概率被交換到最末尾，所以每個元素出現在最末一位的概率都是 1/(i+1) 。而每個數也都有 i/(i+1) 的概率不被交換到最末尾，如果不被交換，從第二次循環開始還原成 i 個數隨機，根據 2. 的假設，它們出現在 i 個位置的概率是 1/i。因此每個數出現在前 i 位任意一位的概率是 (i/(i+1)) * (1/i) = 1/(i+1)，也是 1/(i+1)。

綜合 1. 2. 3. 得出，對于任意 n >= 2，經過這個算法，每個元素出現在 n 個位置任意一個位置的概率都是 1/n。

小結

關于數組亂序，如果面試中被問到，能說出 "Fisher–Yates Shuffle"，并且能基本說出原理（你也看到了，其實代碼非常的簡單），那么基本應該沒有問題了；如果能更進一步，將其證明呈上（甚至一些面試官都可能一時證明不了），那么就牛逼了。千萬不能只會用 Math.random() 投機取巧！

Read More：

數組的完全隨機排列（推薦）

Fisher–Yates Shuffle（推薦）

如何測試洗牌程序

How to randomize (shuffle) a JavaScript array?

Code for Shuffling an Array

云服務器 GPU云服務器數組亂序方法 java面試之io cdn常見面試問題面試問題

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/79901.html

也談面試必備問題之 JavaScript 數組去重

摘要：而數組元素去重是基于運算符的。而如果有迭代函數，則計算傳入迭代函數后的值，對值去重，調用方法，而該方法的核心就是調用方法，和我們上面說的方法一異曲同工。 Why underscore （覺得這部分眼熟的可以直接跳到下一段了...）最近開始看 underscore.js 源碼，并將 underscore.js 源碼解讀放在了我的 2016 計劃中。閱讀一些著名框架類庫的源碼，就好像...

Coly 2019-08-21 10:51 評論0 收藏0
JavaScript專題系列20篇正式完結！

摘要：寫在前面專題系列是我寫的第二個系列，第一個系列是深入系列。專題系列自月日發布第一篇文章，到月日發布最后一篇，感謝各位朋友的收藏點贊，鼓勵指正。寫在前面 JavaScript 專題系列是我寫的第二個系列，第一個系列是 JavaScript 深入系列。 JavaScript 專題系列共計 20 篇，主要研究日常開發中一些功能點的實現，比如防抖、節流、去重、類型判斷、拷貝、最值、扁平、柯里...

sixleaves 2019-08-21 17:15 評論0 收藏0
案例 - 收藏集 - 掘金

摘要：同行這么做使用實現圓形進度條前端掘金在開發微信小程序的時候，遇到圓形進度條的需求。實現也談數組去重前端掘金的數組去重是一個老生常談的話題了。百度前端技術學院自定義前端掘金一標簽概念元素表示用戶界面中項目的標題。閑話圖片上傳 - 掘金作者：孫輝，美團金融前端團隊成員。15年畢業加入美團，相信技術，更相信技術只是大千世界里知識的一種，個人博客: https://sunyuhui.com ...

張金寶 2019-08-20 17:44 評論0 收藏0
案例 - 收藏集 - 掘金

摘要：同行這么做使用實現圓形進度條前端掘金在開發微信小程序的時候，遇到圓形進度條的需求。實現也談數組去重前端掘金的數組去重是一個老生常談的話題了。百度前端技術學院自定義前端掘金一標簽概念元素表示用戶界面中項目的標題。閑話圖片上傳 - 掘金作者：孫輝，美團金融前端團隊成員。15年畢業加入美團，相信技術，更相信技術只是大千世界里知識的一種，個人博客: https://sunyuhui.com ...

huangjinnan 2019-08-29 12:54 評論0 收藏0
JavaScript專題系列文章

摘要：專題系列共計篇，主要研究日常開發中一些功能點的實現，比如防抖節流去重類型判斷拷貝最值扁平柯里遞歸亂序排序等，特點是研究專題之函數組合專題系列第十六篇，講解函數組合，并且使用柯里化和函數組合實現模式需求我們需要寫一個函數，輸入，返回。 JavaScript 專題之從零實現 jQuery 的 extend JavaScritp 專題系列第七篇，講解如何從零實現一個 jQuery 的 ext...

Maxiye 2019-08-21 17:57 評論0 收藏0