題目描述：

給定方法 rand7 可生成 [1,7] 范圍內的均勻隨機整數(shù)，試寫一個方法 rand10 生成 [1,10] 范圍內的均勻隨機整數(shù)。

你只能調用 rand7() 且不能調用其他方法。請不要使用系統(tǒng)的 Math.random() 方法。

每個測試用例將有一個內部參數(shù) n，即你實現(xiàn)的函數(shù) rand10() 在測試時將被調用的次數(shù)。請注意，這不是傳遞給 rand10() 的參數(shù)。

示例 1:
輸入: 1
輸出: [2]

示例 2:
輸入: 2
輸出: [2,8]

示例 3:
輸入: 3
輸出: [3,8,10]

提示:
1 <= n <= 105

進階:
rand7()調用次數(shù)的 期望值 是多少 ?
你能否盡量少調用 rand7() ?

解題思路一：首先說一個結論就是(rand_X() - 1) × Y + rand_Y() ==> [1,X*Y]，即可以等概率的生成[1, X * Y]范圍的隨機數(shù)，其實就像軍訓的時候報數(shù)，Y是每一行的人數(shù)，X是列數(shù)【參考下面的圖】。第二就是拒絕采樣，效果是能夠減少調用rand7()的調用次數(shù)。我們在利用(rand_7() - 1) × 7 + rand_7() ==> [1,7*7]得到rand49()的時候，我們希望能夠等概率的生成[1,10]的隨機數(shù)，那么可以拒絕掉大于40的數(shù)。即if num<=40:才進行采樣。

為了充分利用被拒絕的采樣結果，即舍棄掉[41, 49]這9個數(shù)。我們可以使用a = num - 40得到rand9，從而可以得到(rand_9() - 1) × 7 + rand_7() ==> [1,9*7]得到rand63，從而對rand63進行采樣。這樣之后的就不難理解了。

# The rand7() API is already defined for you.
# def rand7():
# @return a random integer in the range 1 to 7class Solution:def rand10(self):""":rtype: int"""while True:a = rand7()b = rand7()num = (a-1)*7 + b # rand49if num<=40:return num%10 + 1a = num - 40 # rand9b = rand7()num = (a-1)*7 + b # rand63if num<=60:return num%10 + 1a = num - 60 # rand3b = rand7()num = (a-1)*7 + b # rand21if num<=20:return num%10 + 1

時間復雜度：期望時間復雜度為O(1)，但最壞情況下會達到 (∞)（一直被拒絕）。
空間復雜度：O(1)
分析一下rand7()調用次數(shù)的 期望值：
首先調用2次得到a,b
然后拒絕采樣一次概率是9/49
第二次是9/49 * 3/63
第三次是9/49 * 3/63 * 1/21就是進入下一輪while循環(huán)了。所以是一個等比數(shù)列。
$$\begin{array}{rl}a& =2+\frac{9}{49}+\frac{9}{49}?\frac{3}{63}//\text{是每次采樣成功的概率}\\ b& =\frac{9}{49}?\frac{3}{63}?\frac{1}{21}//\text{是每次進入下一輪循環(huán)的概率(等比數(shù)列的公比)}\\ E(\#call)& =a?\frac{1}{1?b}\\ & \approx 2.19333\end{array}\text{\hspace{1em}?}$$
所以期望次數(shù)是2.19332

解題思路二：0

解題思路三：0