题目描述

class Solution {
public:
int rand10() {
int rand40 = 40;
while (rand40 >= 40) {
rand40 = (rand7() - 1) * 7 + rand7() - 1;
}
return rand40 % 10 + 1;
}
};

样例

Example 1:

Input: 1
Output: [7]
Example 2:

Input: 2
Output: [8,4]
Example 3:

Input: 3
Output: [8,1,10]

算法1

(概率) $O(n^2)$

用rand7实现rand10. rand7得到1-7， (rand7-1)*7+rand7-1得到0-48，舍弃41-48，然后模10得到0-9，加一转换成1-10的值域。

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    int rand10() {
        int rand40 = 40;
        while (rand40 >= 40) {
            rand40 = (rand7() - 1) * 7 + rand7() - 1;
        }
        return rand40 % 10 + 1;
    }
};