力扣470.用Rand7()实现Rand10()拒绝采样等概率随机数生成

Problem: 470. 用 Rand7() 实现 Rand10()

文章目录 🍻 k 进制诸位生成 + 拒绝采样🍺 朴素版🍺 优化版 🍻 等概率生成任何数大法

🍻 k 进制诸位生成 + 拒绝采样

👩‍🏫 参考题解

⏰ 时间复杂度：期望复杂度为 O ( 1 ) O(1) O(1)，最坏情况下为 O ( ∞ ) O(∞) O(∞)🌍 空间复杂度： O ( 1 ) O(1) O(1) 🍺 朴素版 class Solution extends SolBase { // k 进制诸位生成 + 拒绝采样 public int rand10() { while(true){ int ans = (rand7()-1) * 7 + rand7() - 1; if(ans >= 1 && ans <= 10){ return ans; } } } } 🍺 优化版

class Solution extends SolBase { // k 进制诸位生成 + 拒绝采样（优化版） public int rand10() { while (true) { int ans = (rand7() - 1) * 7 + (rand7() - 1); // 进制转换 if (1 <= ans && ans <= 40) return ans % 10 + 1; } } } 🍻 等概率生成任何数大法

🧑‍🏫 参考题解 万能解法

⏰ 时间复杂度：期望复杂度为 O ( 1 ) O(1) O(1)，最坏情况下为 O ( ∞ ) O(∞) O(∞)🌍 空间复杂度： O ( 1 ) O(1) O(1) /** * The rand7() API is already defined in the parent class SolBase. * public int rand7(); * @return a random integer in the range 1 to 7 */ class Solution extends SolBase { public int rand10() { // 生成 1～10 的随机数，最大的 10 的二进制是 1010，所以需要调用四次 rand2() int ans = rand2(); // 一位二进制 for (int i = 0; i < 3; i++) { ans <<= 1; ans ^= rand2(); } // 超出范围就重试 return (ans <= 10 && ans > 0) ? ans : rand10(); } // 随机生成 0 和 1 public int rand2() { int ans = rand7(); // 生成 7 进行重新生成 // 生成 1～6 按奇偶数进行分类成两种，即 0 和 1 return ans == 7 ? rand2() : ans % 2; } }