資料結構和演算法面試題系列—隨機演算法總結

摘要： 這個系列是我多年前找工作時對資料結構和演算法總結，其中有基礎部分，也有各大公司的經典的面試題，最早釋出在CSDN。現整理為一個系列給需要的朋友參考，如有錯誤，歡迎指正。本系列完整程式碼地址在 這裡 。 0 概述 隨機演算法涉及大量概率論知識，有時候難得去仔細看推導過程，當然能夠完...

這個系列是我多年前找工作時對資料結構和演算法總結，其中有基礎部分，也有各大公司的經典的面試題，最早釋出在CSDN。現整理為一個系列給需要的朋友參考，如有錯誤，歡迎指正。本系列完整程式碼地址在 ofollow,noindex">這裡 。

0 概述

隨機演算法涉及大量概率論知識，有時候難得去仔細看推導過程，當然能夠完全瞭解推導的過程自然是有好處的，如果不瞭解推導過程，至少記住結論也是必要的。本文總結最常見的一些隨機演算法的題目，是幾年前找工作的時候寫的。需要說明的是，這裡用到的隨機函式 randInt(a, b) 假定它能隨機的產生範圍 [a,b] 內的整數，即產生每個整數的概率相等（雖然在實際中並不一定能實現，不過不要太在意，這個世界很多事情都很隨機）。本文程式碼在 這裡 。

1 隨機排列陣列

假設給定一個數組 A ，它包含元素 1 到 N，我們的目標是構造這個陣列的一個均勻隨機排列。

一個常用的方法是為陣列每個元素 A[i] 賦一個隨機的優先順序 P[i] ，然後依據優先順序對陣列進行排序。比如我們的陣列為 A = {1， 2， 3， 4} ，如果選擇的優先順序陣列為 P = {36， 3， 97， 19} ，那麼就可以得到數列 B={2, 4, 1, 3} ，因為 3 的優先順序最高（為97），而 2 的優先順序最低（為3）。這個演算法需要產生優先順序陣列，還需使用優先順序陣列對原陣列排序，這裡就不詳細描述了，還有一種更好的方法可以得到隨機排列陣列。

產生隨機排列陣列的一個更好的方法是原地排列（ in-place ）給定陣列，可以在 O(N) 的時間內完成。虛擬碼如下：

RANDOMIZE-IN-PLACE ( A , n ) 
for i ←1 to n do 
swap A[i] ↔ A[RANDOM(i , n )]
複製程式碼

如程式碼中所示，第 i 次迭代時，元素 A[i] 是從元素 A[i...n] 中隨機選取的，在第 i 次迭代後，我們就再也不會改變 A[i] 。

A[i] 位於任意位置j的概率為 1/n。這個是很容易推導的，比如 A[1] 位於位置 1 的概率為 1/n ，這個顯然，因為 A[1] 不被1到n的元素替換的概率為 1/n ，而後就不會再改變 A[1] 了。而 A[1] 位於位置 2 的概率也是 1/n ，因為 A[1] 要想位於位置2，則必須在第一次與 A[k] (k=2...n) 交換，同時第二次 A[2] 與 A[k] 替換，第一次與 A[k] 交換的概率為 (n-1)/n ，而第二次替換概率為 1/(n-1) ，所以總的概率是 (n-1)/n * 1/(n-1) = 1/n 。同理可以推導其他情況。

當然這個條件只能是隨機排列陣列的一個必要條件，也就是說，滿足元素 A[i] 位於位置 j 的概率為 1/n 不一定就能說明這可以產生隨機排列陣列。因為它可能產生的排列數目少於 n! ，儘管概率相等，但是排列數目沒有達到要求，演算法導論上面有一個這樣的反例。

演算法 RANDOMIZE-IN-PLACE 可以產生均勻隨機排列，它的證明過程如下：

首先給出k排列的概念，所謂 k 排列就是從n個元素中選取k個元素的排列，那麼它一共有 n!/(n-k)! 個 k 排列。

迴圈不變式：for迴圈第i次迭代前，對於每個可能的i-1排列，子陣列A[1...i-1]包含該i-1排列的概率為 (n-i+1)! / n! 。

• 初始化：在第一次迭代前，i=1，則迴圈不變式指的是對於每個0排列，子陣列A[1...i-1]包含該0排列的概率為 (n-1+1)! / n! = 1 。A[1...0]為空的陣列，0排列則沒有任何元素，因此A包含所有可能的0排列的概率為1。不變式成立。

• 維持：假設在第i次迭代前，陣列的i-1排列出現在 A[1...i-1] 的概率為 (n-i+1) !/ n! ，那麼在第i次迭代後，陣列的所有i排列出現在 A[1...i] 的概率為 (n-i)! / n! 。下面來推導這個結論：

  • 考慮一個特殊的 i 排列 p = {x ₁ , x ₂ , ... x _i }，它由一個 i-1 排列 p' ={x1, x2,..., x _i−1 } 後面跟一個 x _i 構成。設定兩個事件變數E1和E2：

• E1為該演算法將排列 p' 放置到 A[1...i-1] 的事件，概率由歸納假設得知為 Pr(E1) = (n-i+1)! / n! 。

• E2為在第 i 次迭代時將 x _i 放入到 A[i] 的事件。 因此我們得到 i 排列出現在 A[1...i] 的概率為 Pr {E2 ∩ E1} = Pr {E2 | E1} Pr {E1} 。而 Pr {E2 | E1} = 1/(n − i + 1) ，所以 Pr {E2 ∩ E1} = Pr {E2 | E1} Pr {E1}= 1 /(n − i + 1) * (n − i + 1)! / n! = (n − i )! / n! 。

• 結束：結束的時候 i=n+1 ，因此可以得到 A[1...n] 是一個給定 n 排列的概率為 1/n！ 。

C實現程式碼如下：

void randomInPlace(int a[], int n)
{
int i;
for (i = 0; i < n; i++) {
int rand = randInt(i, n-1);
swapInt(a, i, rand);
}
}
複製程式碼

擴充套件

如果上面的隨機排列演算法寫成下面這樣，是否也能產生均勻隨機排列？

PERMUTE-WITH-ALL( A , n ) 
for i ←1 to n do 
swap A[i] ↔A[RANDOM(1 , n )]
複製程式碼

注意，該演算法不能產生均勻隨機排列。假定 n=3 ，則該演算法可以產生 3*3*3=27 個輸出，而3個元素只有 3!=6 個不同的排列，要使得這些排列出現概率等於 1/6 ，則必須使得每個排列出現次數 m 滿足 m/27=1/6 ，顯然，沒有這樣的整數符合條件。而實際上各個排列出現的概率如下，如 {1,2,3} 出現的概率為 4/27 ，不等於 1/6 。

排 列	概 率
<1, 2, 3>	4/27
<1, 3, 2>	5/27
<2, 1, 3>	5/27
<2, 3, 1>	5/27
<3, 1, 2>	4/27
<3, 2, 1>	4/27

2 隨機選取一個數字

題：給定一個未知長度的整數流，如何隨機選取一個數？（所謂隨機就是保證每個數被選取的概率相等）

解1：如果資料流不是很長，可以存在陣列中，然後再從陣列中隨機選取。當然題目說的是未知長度，所以如果長度很大不足以儲存在記憶體中的話，這種解法有其侷限性。

解2：如果資料流很長的話，可以這樣：

• 如果資料流在第1個數字後結束，那麼必選第1個數字。
• 如果資料流在第2個數字後結束，那麼我們選第2個數字的概率為1/2，我們以1/2的概率用第2個數字替換前面選的隨機數，得到新的隨機數。
• ......
• 如果資料流在第n個數字後結束，那麼我們選擇第n個數字的概率為1/n，即我們以1/n的概率用第n個數字替換前面選的隨機數，得到新的隨機數。

一個簡單的方法就是使用隨機函式 f(n)=bigrand()%n ，其中 bigrand() 返回很大的隨機整數，當資料流到第 n 個數時，如果 f(n)==0 ，則替換前面的已經選的隨機數，這樣可以保證每個數字被選中的概率都是 1/n 。如當 n=1 時，則 f(1)=0 ，則選擇第 1 個數，當 n=2 時，則第 2 個數被選中的概率都為 1/2 ，以此類推，當數字長度為 n 時，第 n 個數字被選中的概率為 1/n 。程式碼如下(注：在 Linux/MacOS 下， rand() 函式已經可以返回一個很大的隨機數了，就當做bigrand()用了)：

void randomOne(int n)
{
int i, select = 0;
for (i = 1; i < n; i++) {
int rd = rand() % n;
if (rd == 0) {
select = i;
}
}
printf("%d\n", select);
}
複製程式碼

3 隨機選取M個數字

題： 程式輸入包含兩個整數 m 和 n ，其中 m<n ，輸出是 0~n-1 範圍內的 m 個隨機整數的有序列表，不允許重複。從概率角度來說，我們希望得到沒有重複的有序選擇，其中每個選擇出現的概率相等。

解1：先考慮個簡單的例子，當 m=2，n=5 時，我們需要從 0~4 這 5 個整數中等概率的選取 2 個有序的整數，且不能重複。如果採用如下條件選取： bigrand() % 5 < 2 ，則我們選取 0 的概率為 2/5 。但是我們不能採取同樣的概率來選取 1，因為選取了 0 後，我們應該以 1/4 的概率來選取1，而在沒有選取0的情況下，我們應該以 2/4 的概率選取1。選取的虛擬碼如下：

select = m
remaining = n
for i = [0, n)
if (bigrand() % remaining < select)
print i
select--
remaining--
複製程式碼

只要滿足條件 m<=n ，則程式輸出 m 個有序整數，不多不少。不會多選，因為每選擇一個數， select-- ，這樣當 select 減到 0 後就不會再選了。同時，也不會少選，因為每次都會 remaining-- ，當 select/remaining=1 時，一定會選取一個數。每個子集被選擇的概率是相等的，比如這裡5選2則共有 C(5,2)=10 個子集，如 {0，1}，{0，2}... 等，每個子集被選中的概率都是 1/10 。

更一般的推導，n選m的子集數目一共有 C(n,m) 個，考慮一個特定的 m 序列，如 0...m-1 ，則選取它的概率為 m/n * (m-1)/(n-1)*....1/(n-m+1)=1/C(n,m) ，可以看到概率是相等的。

Knuth 老爺爺很早就提出了這個演算法，他的實現如下：

void randomMKnuth(int n, int m)
{
int i;
for (i = 0; i < n; i++) {
if ((rand() % (n-i)) < m) {
printf("%d ", i);
m--;
}
}
}
複製程式碼

解2：還可以採用前面隨機排列陣列的思想，先對前 m 個數字進行隨機排列，然後排序這 m 個數字並輸出即可。程式碼如下：

void randomMArray(int n, int m)
{
int i, j;
int *x = (int *)malloc(sizeof(int) * n);

for (i = 0; i < n; i++)
x[i] = i;

// 隨機陣列
for (i = 0; i < m; i++) {
j = randInt(i, n-1);
swapInt(x, i, j);
}

// 對陣列前 m 個元素排序
for (i = 0; i < m; i++) {
for (j = i+1; j>0 && x[j-1]>x[j]; j--) {
swapInt(x, j, j-1);
}
}

for (i = 0; i < m; i++) {
printf("%d ", x[i]);
}

printf("\n");
}
複製程式碼

4 rand7 生成 rand10 問題

題：已知一個函式rand7()能夠生成1-7的隨機數，每個數概率相等，請給出一個函式rand10()，該函式能夠生成 1-10 的隨機數，每個數概率相等。

解1：要產生 1-10 的隨機數，我們要麼執行 rand7() 兩次，要麼直接乘以一個數字來得到我們想要的範圍值。如下面公式(1)和（2）。

idx = 7 * (rand7()-1) + rand7() ---(1) 正確
idx = 8 * rand7() - 7---(2) 錯誤
複製程式碼

上面公式 (1) 能夠產生 1-49 的隨機數，為什麼呢？因為 rand7() 的可能的值為 1-7，兩個 rand7() 則可能產生 49 種組合，且正好是 1-49 這 49 個數，每個數出現的概率為 1/49 ，於是我們可以將大於 40 的丟棄，然後取 (idx-1) % 10 + 1 即可。公式（2）是錯誤的，因為它生成的數的概率不均等，而且也無法生成49個數字。

1234567
11234567
289 101234
356789 101
42345678
59 1012345
66789 10**
7*******
複製程式碼

該解法基於一種叫做拒絕取樣的方法。主要思想是隻要產生一個目標範圍內的隨機數，則直接返回。如果產生的隨機數不在目標範圍內，則丟棄該值，重新取樣。由於目標範圍內的數字被選中的概率相等，這樣一個均勻的分佈生成了。程式碼如下：

int rand7ToRand10Sample() {
int row, col, idx;
do {
row = rand7();
col = rand7();
idx = col + (row-1)*7;
} while (idx > 40);

return 1 + (idx-1) % 10;
}
複製程式碼

由於row範圍為1-7，col範圍為1-7，這樣idx值範圍為1-49。大於40的值被丟棄，這樣剩下1-40範圍內的數字，通過取模返回。下面計算一下得到一個滿足1-40範圍的數需要進行取樣的次數的期望值：

E(# calls to rand7) = 2 * (40/49) +
4 * (9/49) * (40/49) +
6 * (9/49)2 * (40/49) +
...

∞
= ∑ 2k * (9/49)k-1 * (40/49)
k=1

= (80/49) / (1 - 9/49)2
= 2.45
複製程式碼

解2：上面的方法大概需要2.45次呼叫 rand7 函式才能得到 1 個 1-10 範圍的數，下面可以進行再度優化。對於大於40的數，我們不必馬上丟棄，可以對 41-49 的數減去 40 可得到 1-9 的隨機數，而rand7可生成 1-7 的隨機數，這樣可以生成 1-63 的隨機數。對於 1-60 我們可以直接返回，而 61-63 則丟棄，這樣需要丟棄的數只有3個，相比前面的9個，效率有所提高。而對於61-63的數，減去60後為 1-3，rand7 產生 1-7，這樣可以再度利用產生 1-21 的數，對於 1-20 我們則直接返回，對於 21 則丟棄。這時，丟棄的數就只有1個了，優化又進一步。當然這裡面對rand7的呼叫次數也是增加了的。程式碼如下，優化後的期望大概是 2.2123。

int rand7ToRand10UtilizeSample() {
int a, b, idx;
while (1) {
a = randInt(1, 7);
b = randInt(1, 7);
idx = b + (a-1)*7;
if (idx <= 40)
return 1 + (idx-1)%10;

a = idx-40;
b = randInt(1, 7);
// get uniform dist from 1 - 63
idx = b + (a-1)*7;
if (idx <= 60)
return 1 + (idx-1)%10;

a = idx-60;
b = randInt(1, 7);
// get uniform dist from 1-21
idx = b + (a-1)*7;
if (idx <= 20)
return 1 + (idx-1)%10;
}
}
複製程式碼

5 趣味概率題

1）稱球問題

題： 有12個小球，其中一個是壞球。給你一架天平，需要你用最少的稱次數來確定哪個小球是壞的，並且它到底是輕了還是重了。

解： 之前有總結過二分查詢演算法，我們知道二分法可以加快有序陣列的查詢。相似的，比如在數字遊戲中，如果要你猜一個介於 1-64 之間的數字，用二分法在6次內肯定能猜出來。但是稱球問題卻不同。稱球問題這裡 12 個小球，壞球可能是其中任意一個，這就有 12 種可能性。而壞球可能是重了或者輕了這2種情況，於是這個問題一共有 12*2 = 24 種可能性。每次用天平稱，天平可以輸出的是 平衡、左重、右重 3 種可能性，即稱一次可以將問題可能性縮小到原來的 1/3 ，則一共 24 種可能性可以在 3 次內稱出來( 3^3 = 27 )。

為什麼最直觀的稱法 6-6 不是最優的？在 6-6 稱的時候，天平平衡的可能性是0，而最優策略應該是讓天平每次稱量時的概率均等，這樣才能三等分答案的所有可能性。

具體怎麼實施呢？ 將球編號為1-12，採用 4, 4 稱的方法。

• 我們先將 1 2 3 4 和 5 6 7 8 進行第1次稱重。
• 如果第1次平衡，則壞球肯定在 9-12 號中。則此時只剩下 9-12 4個球，可能性為 9- 10- 11- 12- 9+ 10+ 11+ 12+ 這8種可能。接下來將 9 10 11 和 1 2 3 稱第2次：如果平衡，則 12 號小球為壞球，將12號小球與1號小球稱第3次即可確認輕還是重。如果不平衡，則如果重了說明壞球重了，繼續將9和10號球稱量，重的為壞球，平衡的話則11為壞球。
• 如果第1次不平衡，則壞球肯定在 1-8 號中。則還剩下的可能性是 1+ 2+ 3+ 4+ 5- 6- 7- 8- 或者 1- 2- 3- 4- 5+ 6+ 7+ 8+ ，如果是 1 2 3 4 這邊重，則可以將 1 2 6 和 3 4 5 稱，如果平衡，則必然是 7 8 輕了，再稱一次7和1，便可以判斷7和8哪個是壞球了。如果不平衡，假定是 1 2 6 這邊重，則可以判斷出 1 2 重了或者 5 輕了，為什麼呢？因為如果是 3+ 4+ 6- ，則 1 2 3 4 比 5 6 7 8 重，但是 1 2 6 應該比 3 4 5 輕。其他情況同理，最多3次即可找出壞球。

下面這個圖更加清晰說明了這個原理。

2）生男生女問題

題：在重男輕女的國家裡，男女的比例是多少？在一個重男輕女的國家裡，每個家庭都想生男孩，如果他們生的孩子是女孩，就再生一個，直到生下的是男孩為止。這樣的國家，男女比例會是多少？

解：還是1：1。在所有出生的第一個小孩中，男女比例是1：1；在所有出生的第二個小孩中，男女比例是1：1；.... 在所有出生的第n個小孩中，男女比例還是1：1。所以總的男女比例是1：1。

3）約會問題

題：兩人相約5點到6點在某地會面，先到者等20分鐘後離去，求這兩人能夠會面的概率。

解：設兩人分別在5點X分和5點Y分到達目的地，則他們能夠會面的條件是 |X-Y| <= 20 ，而整個範圍為 S={(x, y): 0 =< x <= 60,  0=< y <= 60} ，如果畫出座標軸的話，會面的情況為座標軸中表示的面積，概率為 (60^2 - 40^2) / 60^2 = 5/9 。

4）帽子問題

題：有n位顧客，他們每個人給餐廳的服務生一頂帽子，服務生以隨機的順序歸還給顧客，請問拿到自己帽子的顧客的期望數是多少？

解：使用指示隨機變數來求解這個問題會簡單些。定義一個隨機變數X等於能夠拿到自己帽子的顧客數目，我們要計算的是 E[X] 。對於 i=1, 2 ... n ，定義 X _i =I {顧客i拿到自己的帽子}，則 X=X ₁ +X ₂ +...X _n 。由於歸還帽子的順序是隨機的，所以每個顧客拿到自己帽子的概率為1/n，即 P _r (X _i =1)=1/n，從而 E(X _i )=1/n，所以E(X)=E(X ₁ + X ₂ + ...X _n )= E(X ₁ )+E(X ₂ )+...E(X _n )=n*1/n = 1，即大約有1個顧客可以拿到自己的帽子。

5）生日悖論

題：一個房間至少要有多少人，才能使得有兩個人的生日在同一天？

解：對房間k個人中的每一對(i, j)定義指示器變數 X _ij = {i與j生日在同一天} ，則i與j生日相同時，X _ij =1，否則 X _ij =0。兩個人在同一天生日的概率 Pr(X _ij =1)=1/n 。則用X表示同一天生日的兩人對的數目，則 E(X)=E(∑k _i=1 ∑k _j=i+1 X _ij ) = C(k,2)*1/n = k(k-1)/2n，令 k(k-1)/2n >=1 ，可得到 k>=28 ，即至少要有 28 個人，才能期望兩個人的生日在同一天。

6）概率逆推問題

題：如果在高速公路上30分鐘內看到一輛車開過的機率是0.95，那麼在10分鐘內看到一輛車開過的機率是多少？(假設常概率條件下)

解：假設10分鐘內看到一輛車開過的概率是x，那麼沒有看到車開過的概率就是1-x，30分鐘沒有看到車開過的概率是 (1-x)^3 ，也就是 0.05 。所以得到方程 (1-x)^3 = 0.05 ，解方程得到 x 大約是 0.63。

參考資料

• 演算法導論第6章隨機演算法
• 程式設計珠璣第12章
• leetcode.com/articles/im…
• mindhacks.cn/2008/06/13/…
• blog.csdn.net/wxwtj/artic…