LeetCode刷题之洗牌算法
2021/11/22 11:10:16
本文主要是介绍LeetCode刷题之洗牌算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
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
这篇关于LeetCode刷题之洗牌算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-07Dify + TiDB Vector,快速构建你的AI Agent
- 2024-07-06有没有什么开源的py项目可以对图像进行分类-icode9专业技术文章分享
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享