題目
題目:有n個(gè)人,圍成一個(gè)環(huán)，編號(hào)為 0、1、2、3、、、n-1，從第一個(gè)人開始循環(huán)報(bào)數(shù)(從1開始)，假設(shè)數(shù)到m的那個(gè)人出列，然后從下一個(gè)人繼續(xù)數(shù)數(shù)，數(shù)到m出列，以此循環(huán)，最后那個(gè)人為勝利者，求勝利者的編號(hào)。
這其實(shí)就是有名的約瑟夫問題。
輸入示例
- n=4, m=3 result=0
- n=50, m=20 result=33
- n=100, m=37 result=44
思路
解法一--模擬法
可以使用數(shù)組或者鏈表來模擬這n個(gè)人，每次刪除第m個(gè)人，直到只剩下一個(gè)人為止。
使用數(shù)組刪除元素的復(fù)雜度較高，鏈表是最優(yōu)選擇，C++ stl中的鏈表用的不太熟練，所以自己寫一個(gè)。為了刪除方便，選擇雙向鏈表，單向鏈表刪除的時(shí)候還需要兩個(gè)指針，很麻煩。
class Solution {
public:
struct Node{
int val;
Node* next;
Node* parent;
}; // 鏈表節(jié)點(diǎn)
int LastRemaining_Solution(int n, int m)
{
if(m == 0 || n == 0)
return -1; // 無效情況返回-1
// 為所有節(jié)點(diǎn)分配空間
vector<Node> node(n);
//頭節(jié)點(diǎn)單獨(dú)賦值
node[0].val = 0;
//構(gòu)造鏈表
for(int i=1;i<n;i++){
node[i].val = i; //編號(hào)
node[i].next = NULL;
node[i-1].next = &node[i];
node[i].parent = &node[i-1];
}
node[n-1].next = &node[0];
node[0].parent = &node[n-1];
//模擬
int num = n; //還剩下的人數(shù)
Node *head = &node[0]; //頭節(jié)點(diǎn)
//在只剩下一個(gè)人的時(shí)候停止模擬
while(num > 1){
// 找到第m個(gè)
int count = 0;
while(count < m-1){
head = head->next;
count ++;
}
//找到了第m個(gè) 開始刪除
head->parent->next = head->next;
head->next->parent = head->parent;
head = head->next;
num --; // 剩余人數(shù)減1
}
return head->val;
}
};
這種算法時(shí)間復(fù)雜度為O(mn)，空間復(fù)雜度為O(n)。
解法二--數(shù)學(xué)推導(dǎo)
感覺應(yīng)該存在某種規(guī)律，但我等數(shù)學(xué)渣渣并不能夠推導(dǎo)出來。
看完書上的解答，表示有點(diǎn)繞，現(xiàn)在用自己的話解釋一遍：
f(n,m):表示 每次在n個(gè)數(shù)字0，1,...,n-1中刪除第m個(gè)數(shù)字最后剩下的數(shù)字（也就是要求的結(jié)果）。（注意，要求數(shù)字標(biāo)號(hào)需要是連續(xù)的，所以后面刪除一個(gè)元素后標(biāo)號(hào)不連續(xù)了，需要重新標(biāo)號(hào)）。
在這n個(gè)數(shù)字中，第一個(gè)被刪除的數(shù)字是 (m-1)%n (取余的原因是m可能比n大)，記作k，則k=(m-1)%n。刪除后的序列為 0,1,...,k-1,k+1,...,n-1。由于下一次刪除是從k+1開始計(jì)數(shù)的，所以相當(dāng)于從標(biāo)號(hào)為k+1,k+2,...,n-1,0,1,2,...,k-1的序列中繼續(xù)刪除第m個(gè)數(shù)字，最終剩下的數(shù)字就是結(jié)果。
剩下的n-1個(gè)數(shù)字如果重新按順序標(biāo)號(hào)得到序列0,1,...,n-2，則每次刪除第m個(gè)數(shù)，最后剩下的數(shù)字就是f(n-1,m)。由于重新標(biāo)號(hào)了，所以并不是f(n,m)=f(n-1,m)! 那么f(n-1,m)對(duì)應(yīng)的數(shù)字在修改標(biāo)號(hào)之前是什么數(shù)呢？
事實(shí)上，原先的不連續(xù)的序列A(k+1,k+2,...,n-1,0,1,2,...,k-1)變成了序列B(0,1,...,n-2)，而我們主要是想知道如何從序列B中的某個(gè)數(shù)找到序列A中對(duì)應(yīng)的關(guān)系，先建立個(gè)映射表格：
| B序列 | 序列A |
|---|---|
| 0 | k+1 |
| 1 | k+2 |
| n-k-2 | n-1 |
| n-k-1 | 0 |
| n-k | 1 |
| n-2 | k-1 |
| f(n-1,m) | (f(n-1,m)+k+1)%n |
根據(jù)表格，可以很直觀的看出，在B序列中數(shù)字x，對(duì)應(yīng)于A序列中的(x+k+1)%n（注意：必須取余數(shù)，因?yàn)锽序列中為n-k,而n-k+k+1為n+1,必須取余數(shù)才能得到1）。所以在B序列中標(biāo)號(hào)為f(n-1,m)，對(duì)于在A序列中就為(f(n-1,m)+k+1)%n。
還記得k嗎，k就是在第一次刪除的時(shí)候刪掉的數(shù)(與n有關(guān)的變量)，k=(m-1)%n。
將其帶入上面的式子，就得到:
(f(n-1,m)+k+1)%n = (f(n-1,m)+(m-1)+1)%n = (f(n-1,m)+m)%n
因此，我們就得到了這個(gè)遞歸公式，而當(dāng)n=1的時(shí)候，也就是序列中只有標(biāo)號(hào)為0的數(shù)字，顯然最后剩下的數(shù)字就是0，所以整個(gè)公式就是：
根據(jù)這個(gè)公式，寫代碼就很簡(jiǎn)單了。
class Solution {
public:
int LastRemaining_Solution(int n, int m)
{
if(m == 0 || n == 0)
return -1; // 無效情況返回-1
int last = 0;
for(int i=2;i<=n;i++)
last = (last+m) % i;
return last;
}
};
這種算法的時(shí)間復(fù)雜度是O(n)，空間復(fù)雜度是O(1)，遠(yuǎn)遠(yuǎn)優(yōu)于第一種算法，但是推導(dǎo)復(fù)雜，數(shù)學(xué)渣渣表示如果沒見過這個(gè)題，絕對(duì)推導(dǎo)不出來。。。
總結(jié)
使用鏈表模擬的常規(guī)解法必須掌握，數(shù)學(xué)推導(dǎo)，那就看狀態(tài)吧。。
