LeetCode刷题之洗牌算法
1.洗牌算法的思路
共有 n 个不同的数,根据每个位置能够选择什么数,共有 n! 种组合。
题目要求每次调用 shuffle 时等概率返回某个方案,或者说每个元素都够等概率出现在每个位置中。
我们可以使用 Knuth 洗牌算法,在 O(n) 复杂度内等概率返回某个方案。
具体的,我们从前往后尝试填充 [0, n - 1][0,n−1] 该填入什么数时,通过随机当前下标与(剩余的)哪个下标进行值交换来实现。
对于下标 x 而言,我们从 [x, n - 1][x,n−1] 中随机出一个位置与 x 进行值交换,当所有位置都进行这样的处理后,我们便得到了一个公平的洗牌方案。
对于下标为 00 位置,从 [0, n - 1][0,n−1] 随机一个位置进行交换,共有 nn 种选择;下标为 11 的位置,从 [1, n - 1][1,n−1] 随机一个位置进行交换,共有 n - 1n−1 种选择 ... 且每个位置的随机位置交换过程相互独立。
2.具体题目
2.1 LeetCode之384打乱数组
-
代码实现
-
/* * @lc app=leetcode.cn id=384 lang=cpp * * [384] 打乱数组 */ // @lc code=start class Solution { public: Solution(vector<int>& nums) { int len = nums.size(); l = len; for (int i = 0; i < len; i++) { num.push_back(nums[i]); ass.push_back(nums[i]); } } vector<int> reset() { return ass; } vector<int> shuffle() { for(int i=0; i<l-1; i++) { int r = rand() % (l-i) + i; int temp = num[i]; num[i] = num[r]; num[r] = temp; } return num; } private: int l; vector<int> num; vector<int> ass; }; /** * 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(); */ // @lc code=end