384. 打亂數組

給你一個整數數組 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
• -$10^6$ <= nums[i] <= $10^6$
• nums 中的所有元素都是 唯一的
• 最多可以調用 5 * $10^4$ 次 reset 和 shuffle

解題思路

1. 對于 int[] reset() 需要重設數組到它的初始狀態并返回，因此我們需要使用一個變量記錄初始的數組。
2. 對于int[] shuffle() 需要返回數組隨機打亂后的結果，因此我們可以從后往前遍歷原數組，例如對于下標size-1，通過產生一個[0,size-1]隨機數，隨機選出一個下標，將其對應的元素與當前下標對應的元素進行交換，那么就完成了隨機數組第一個元素的選擇。對于第二個元素，也是采用同樣的方法，隨機選出[0,size-2]中的一個元素進行填充，不斷循環，直到將隨機數組填充完成，這樣就可以保證每一個元素的位置都隨機選出的。

代碼

class Solution {
public:vector<int> old;Solution(vector<int>& nums) {old=nums;}vector<int> reset() {return old;}vector<int> shuffle() {auto temp=old;for (int i = temp.size(); i >=1 ; --i) {swap(temp[rand()%i],temp[i-1]);}return temp;}
};/*** Your Solution object will be instantiated and called as such:* Solution* obj = new Solution(nums);* vector<int> param_1 = obj->reset();* vector<int> param_2 = obj->shuffle();*/