0_Fisher-Yates洗牌算法

• 编程语言中伪随机数的生成
• 暴力法
• 
  
• 将每个数放到一个帽子里面，每次从帽子里随机摸一个数出来，直到帽子为空，摸出来的数按照顺序放入数组，这恰好是我们要的洗牌后的数组。
• 算法：
• 首先把数组arr复制一份给copy数组
• 之后每次从copy中取一个数，为了防止被重复取出，每次取完将这个数从copy中删除
• Fisher-Yates洗牌算法
• 将数组中的元素互换，避免每次迭代中用于修改列表的时间
• 算法：
• 类似于暴力搜索算法，每次迭代中，生成一个当前下标到数组末尾下标之间的随机整数
• 将当前元素和随机选出的下标所指的元素互相交换（当前元素可与自身交换）
  /LeetCode: 384 Shuffle an ArrayDescription:Given an integer array nums, design an algorithm to randomly shuffle the array.
  Implement the Solution class:-Solution(int[] nums) : Initializes the object with the integer array nums.-int[] reset() : Resets the array to its original configuration and returns it.-int[] shuffle() : Returns a random shuffling of the array.
  Constraints:1 <= nums.length <= 200-10^6 <= nums[i] <= 10^6All the elements of nums are unique.At most 5 10^4 calls will be made to reset and shuffle./class Solution {private: vector arr; vector origin;public: Solution(vector& nums) { this->arr.assign(nums.begin(),nums.end()); this->origin = nums; } /** Resets the array to its original configuration and return it. / vector reset() { arr.clear(); arr.assign(origin.begin(),origin.end()); return arr; } /* Returns a random shuffling of the array. / vector shuffle() { int N = arr.size(); int randIdx = 0; //srand(time(0)); for (int i = 0; i < N; i++) { randIdx = (rand() % (N - i)) + i; swap(arr[i], arr[randIdx]); } return arr; }};