今天是堅持每日一題打卡的第二十三天

---

題目鏈接：https://leetcode-cn.com/problems/shuffle-an-array/

---

題解匯總：https://zhanglong.blog.csdn.net/article/details/121071779

---

題目描述

給你一個整數數組 nums ，設計算法來打亂一個沒有重復元素的數組。

實現 Solution class:

Solution(int[] nums) 使用整數數組 nums 初始化對象
int[] reset() 重設數組到它的初始狀態并返回
int[] shuffle() 返回數組隨機打亂后的結果

示例：
輸入
[“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]

提示：
1 <= nums.length <= 200
-106 <= nums[i] <= 106
nums 中的所有元素都是 唯一的
最多可以調用 5 * 104 次 reset 和 shuffle

---

關鍵思路在于，如何設計一個隨機算法，使每個數落在任意位置上的概率為1/n， 并且可以在數學上證明它。

算法詳細解析：https://zhanglong.blog.csdn.net/article/details/121470512

---

class Solution { private:vector<int> res;vector<int> root; public:Solution(vector<int>& nums) {for (auto i : nums) res.push_back(i);root = res;}vector<int> reset() {return root;}vector<int> shuffle() {int len = res.size();for (int i = 0; i < len; i++) {swap(res[i], res[rand() % (len + 1)]);}return res;} };

---

這就是我喜歡算法的原因。在我眼里，算法從來不是枯燥的邏輯堆砌，而是神一樣的邏輯創造。 盡管這個世界很復雜，但竟也如此的簡潔，優雅。??????——Knuth

總結

以上是生活随笔為你收集整理的【解题报告】Leecode 384. 打乱数组——Leecode每日一题系列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。