約瑟夫環(huán)問題算是很經(jīng)典的題了添吗，估計大家都聽說過，然后我就在一次筆試中遇到了悠汽，下面我就用 3 種方法來詳細(xì)講解一下這道題潜圃，最后一種方法學(xué)了之后保證讓你可以讓你裝逼缸棵。
問題描述：編號為 1-N 的 N 個士兵圍坐在一起形成一個圓圈，從編號為 1 的士兵開始依次報數(shù)（1谭期，2蛉谜，3…這樣依次報），數(shù)到 m 的 士兵會被殺死出列崇堵，之后的士兵再從 1 開始報數(shù)。直到最后剩下一士兵客燕，求這個士兵的編號鸳劳。
1、方法一：數(shù)組
在大一第一次遇到這個題的時候也搓，我是用數(shù)組做的赏廓，我猜絕大多數(shù)人也都知道怎么做涵紊。方法是這樣的：
用一個數(shù)組來存放 1，2幔摸，3 … n 這 n 個編號摸柄，如圖（這里我們假設(shè)n = 6, m = 3）
然后不停著遍歷數(shù)組，對于被選中的編號既忆，我們就做一個標(biāo)記驱负，例如編號 arr[2] = 3 被選中了，那么我們可以做一個標(biāo)記患雇，例如讓 arr[2] = -1跃脊，來表示 arr[2] 存放的編號已經(jīng)出局的了。
然后就按照這種方法苛吱，不停著遍歷數(shù)組酪术，不停著做標(biāo)記，直到數(shù)組中只有一個元素是非 -1 的翠储，這樣绘雁，剩下的那個元素就是我們要找的元素了。我演示一下吧：
這種方法簡單嗎援所？思路簡單庐舟，但是編碼卻沒那么簡單，臨界條件特別多任斋，每次遍歷到數(shù)組最后一個元素的時候继阻，還得重新設(shè)置下標(biāo)為 0，并且遍歷的時候還得判斷該元素時候是否是 -1废酷。感興趣的可以動手寫一下代碼瘟檩，用這種數(shù)組的方式做，千萬不要覺得很簡單澈蟆，編碼這個過程還是挺考驗(yàn)人的墨辛。
這種做法的時間復(fù)雜度是 O(n * m), 空間復(fù)雜度是 O(n);
2、方法二：環(huán)形鏈表
學(xué)過鏈表的人趴俘，估計都會用鏈表來處理約瑟夫環(huán)問題睹簇，用鏈表來處理其實(shí)和上面處理的思路差不多，只是用鏈表來處理的時候寥闪，對于被選中的編號太惠，不再是做標(biāo)記，而是直接移除疲憋，因?yàn)閺逆湵硪瞥粋€元素的時間復(fù)雜度很低凿渊，為 O(1)。當(dāng)然，上面數(shù)組的方法你也可以采用移除的方式埃脏，不過數(shù)組移除的時間復(fù)雜度為 O(n)搪锣。所以采用鏈表的解決方法如下：
1、先創(chuàng)建一個環(huán)形鏈表來存放元素：
2彩掐、然后一邊遍歷鏈表一遍刪除构舟，直到鏈表只剩下一個節(jié)點(diǎn)，我這里就不全部演示了
代碼如下：
// 定義鏈表節(jié)點(diǎn)
class Node{
int date;
Node next;
public Node(int date) {
this.date = date;
}
}
核心代碼
public static int solve(int n, int m) {
if(m == 1 || n < 2)
return n;
// 創(chuàng)建環(huán)形鏈表
Node head = createLinkedList(n);
// 遍歷刪除
int count = 1;
Node cur = head;
Node pre = null;//前驅(qū)節(jié)點(diǎn)
while (head.next != head) {
// 刪除節(jié)點(diǎn)
if (count == m) {
count = 1;
pre.next = cur.next;
cur = pre.next;
} else {
count++;
pre = cur;
cur = cur.next;
}
}
return head.date;
}
static Node createLinkedList(int n) {
Node head = new Node(1);
Node next = head;
for (int i = 2; i <= n; i++) {
Node tmp = new Node(i);
next.next = tmp;
next = next.next;
}
// 頭尾串聯(lián)
next.next = head;
return head;
}
這種方法估計是最多人用的堵幽，時間復(fù)雜度為 O(n * m),空間復(fù)雜度是 O(n)狗超。
還有更好的方法嗎？答有谐檀，請往下看
方法三：遞歸
其實(shí)這道題還可以用遞歸來解決抡谐，遞歸是思路是每次我們刪除了某一個士兵之后，我們就對這些士兵重新編號桐猬，然后我們的難點(diǎn)就是找出刪除前和刪除后士兵編號的映射關(guān)系麦撵。
我們定義遞歸函數(shù) f(n，m) 的返回結(jié)果是存活士兵的編號溃肪，顯然當(dāng) n = 1 時免胃，f(n, m) = 1。假如我們能夠找出 f(n惫撰，m) 和 f(n-1羔沙，m) 之間的關(guān)系的話，我們就可以用遞歸的方式來解決了厨钻。我們假設(shè)人員數(shù)為 n, 報數(shù)到 m 的人就自殺扼雏。則剛開始的編號為
…
m - 1
m
m + 1
m + 2
進(jìn)行了一次刪除之后，刪除了編號為 m 的節(jié)點(diǎn)夯膀。刪除之后诗充，就只剩下 n - 1 個節(jié)點(diǎn)了，刪除前和刪除之后的編號轉(zhuǎn)換關(guān)系為：
刪除前 --- 刪除后
… --- …
m - 2 --- n - 2
m - 1 --- n - 1
m ---- 無(因?yàn)榫幪柋粍h除了)
m + 1 --- 1(因?yàn)橄麓尉蛷倪@里報數(shù)了)
m + 2 ---- 2
… ---- …
新的環(huán)中只有 n - 1 個節(jié)點(diǎn)诱建。且刪除前編號為 m + 1, m + 2, m + 3 的節(jié)點(diǎn)成了刪除后編號為 1蝴蜓， 2， 3 的節(jié)點(diǎn)俺猿。
假設(shè) old 為刪除之前的節(jié)點(diǎn)編號茎匠， new 為刪除了一個節(jié)點(diǎn)之后的編號，則 old 與 new 之間的關(guān)系為 old = (new + m - 1) % n + 1押袍。
這樣诵冒，我們就得出 f(n, m) 與 f(n - 1, m)之間的關(guān)系了，而 f(1, m) = 1.所以我們可以采用遞歸的方式來做谊惭。代碼如下：
注：有些人可能會疑惑為什么不是 old = (new + m ) % n 呢钙畔？主要是因?yàn)榫幪柺菑?1 開始的，而不是從 0 開始的驮履。如果 new + m == n的話苦锨，會導(dǎo)致最后的計算結(jié)果為 old = 0。所以 old = (new + m - 1) % n + 1.
int f(int n, int m){ if(n == 1) return n; return (f(n - 1, m) + m - 1) % n + 1;}
我去药磺，兩行代碼搞定告组，而且時間復(fù)雜度是 O(n)，空間復(fù)雜度是O(1)癌佩，牛逼木缝！那如果你想跟別人說，我想一行代碼解決約瑟夫問題呢围辙？答是沒問題的我碟，如下：
int f(int n, int m){ return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;}
臥槽，以后面試官讓你手寫約瑟夫問題姚建，你就扔這一行代碼給它矫俺。
總結(jié)
不過那次筆試時，并沒有用遞歸的方法做掸冤，而是用鏈表的方式做厘托，，稿湿，铅匹，，那時饺藤，不知道原來還能用一行代碼搞定的包斑，，涕俗，罗丰，歡迎各位大佬提供半行代碼搞定的方法！
