给你一个整数数组 nums
,设计算法来打乱一个没有重复元素的数组。打乱后,数组的所有排列应该是 等可能 的。
实现 Solution
class:
Solution(int[] nums)
使用整数数组nums
初始化对象int[] reset()
重设数组到它的初始状态并返回int[] shuffle()
返回数组随机打乱后的结果
示例 1:
输入 ["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 <= 50
-106 <= nums[i] <= 106
nums
中的所有元素都是 唯一的- 最多可以调用
104
次reset
和shuffle
模板题,洗牌算法。
思路:从前向后扫描数据,把位置i的数据随机插入到前i个(包括第i个)位置中(假设为k)
原数组的第 i 个元素(随机到的数)在新数组的前 i 个位置的概率都是:(1/i) * [i/(i+1)] * [(i+1)/(i+2)] *…* [(n-1)/n] = 1/n,(即第i次刚好随机放到了该位置,在后面的n-i 次选择中该数字不被选中)。
原数组的第 i 个元素(随机到的数)在新数组的 i+1 (包括i + 1)以后的位置(假设是第k个位置)的概率是:(1/k) * [k/(k+1)] * [(k+1)/(k+2)] *…* [(n-1)/n] = 1/n
class Solution { public: vector<int> record; Solution(vector<int>& nums) { record=nums; } vector<int> reset() { return record; } vector<int> shuffle() { vector<int> ans=record; for(int i=0;i<ans.size();i++) { int n=rand()%(i+1); if(i!=n) { swap(ans[i],ans[n]); } } return ans; } }; /** * 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(); */
原文地址:http://www.cnblogs.com/zzzlight/p/16916495.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性