題目描述：

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

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

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

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

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

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

提示:
1 <= n <= 105

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

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

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

# 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

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

解題思路二：0

解題思路三：0