主題

LeetCode - 384. Shuffle an Array 解題心得

Not In My Back Yard | 2021-10-25 00:00:03 | 巴幣 2 | 人氣 82

題目連結:


題目意譯:
給定一整數陣列 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> 函式庫就比較不會有這問題。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作