題目連結：
題目意譯：
給定一整數陣列 nums，設計一個演算法去將陣列隨機地洗牌（重新排列）。
實作類別 Solution：
Solution(int[] nums) 初始化物件有著整數陣列 nums。
int[] reset() 重設陣列到原始的設定並回傳它。
int[] shuffle() 回傳一個陣列的隨機洗牌之排列。
限制：
1 ≦ nums.length ≦ 200
-10 ^ 6 ≦ nums[i] ≦ 10 ^ 6
nums 中的元素皆相異。
最多 5 × 10 ^ 4 次呼叫為 reset 和 shuffle。
範例測資：
範例 1：
輸入
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
輸出
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]
解釋
Solution solution = new Solution([1, 2, 3]);
solution.shuffle(); // 洗牌陣列 [1,2,3] 並回傳其為結尾。[1,2,3] 之任意排列必須有著相同可能性被回傳。例如：回傳 [3, 1, 2]
solution.reset(); // 重設陣列到其原始設定 [1,2,3]。回傳 [1, 2, 3]
solution.shuffle(); // 回傳陣列 [1,2,3] 的隨機洗牌。例如：回傳 [1, 3, 2]
解題思維：
費雪－葉慈洗牌（Fisher–Yates Shuffle）演算法即是相當經典、常見的洗牌演算法，其流程如下：
假設現在要隨機地重新排列之陣列 nums ，其長度為 n（索引值從 0 開始）。
則我們可以從 nums[n - 1] 開始，從 0 ～ n - 1 （含端點）之中隨機挑出一個數字 i ，然後將 nums[n - 1] 與 nums[i] 交換。
之後我們便將 n 減去 1（注意不是真的去更動陣列長度），然後重複以上步驟直到 n 變為 1 為止。
例如 nums = [1,2,3] ，因此 n = 3。我們從 nums[2] 開始：
從 0 ～ 2 中挑一個數字。此時假設我們挑到 0，因此我們將 nums[2] 與 nums[0] 交換，得 nums = [3,2,1]。將 n 減去 1 得 n = 2。
從 0 ～ 1 中挑一個數字。此時假設我們挑到 1，因此我們將 nums[1] 與 nums[1] 交換（即不變），得 nums = [3,2,1]。將 n 減去 1 得 n = 1。此時便結束了洗牌流程。
因此如上我們便得到了 [3,2,1] 這個排列。
可以看到這個演算法在剩下 k 個數字時，也就是目前在 nums[k - 1] 時，會有著 k 個可能的選擇。因此，從 k = n 開始，我們每一次的可能選擇數的乘積將是
n × (n - 1) × (n - 2) × …… × 1
即 n!（n 階乘），也就是 n 個物件的可能排列之方法數。
也因此，每個排列將有著均等的機率在過程中產生。不過前提是我們在挑 0 ～ k 中的數字時，每個數字被挑中的機率應均等。
如果是使用 C++ 內建的 rand() 則很有可能會讓某些數字被挑中的機率較大，因此可以參見以前的文章（這篇、這篇以及這篇的棄卻抽樣（Rejection Sampling）），不過改用 C++11 的 <random> 函式庫就比較不會有這問題。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
